ICPC 2019 Asia Yokohama Regional 参加記

2019年11月15日及び16日に行われた、ICPC 2019 Asia Yokohama Regionalに参加しました。nicklawさん(参加記はこちら)とNOSSさん(参加記はこちら)と私でチームEldoradoとして出場しました。結果は4完で65チーム中23位でした。

1日目

リハーサル前

いつもどおり箱そばを食べて駅メモをしながら会場に向かいました（ステマ（ステマではない（こういうのなんて言うんですか？）））。

SOUL FOOD pic.twitter.com/TrqzyJYra3

— まほろば (@mhrb_minase) 2019年11月16日

しいらと日本大通りにおでかけしたよ！ https://t.co/22j5hRW4xt

— まほろば (@mhrb_minase) 2019年11月16日

日常ですね。
チームメイトと合流し、会場入りしました。

pic.twitter.com/trFheiae8K

— まほろば (@mhrb_minase) 2019年11月16日

リハーサル

nicklawさんが環境構築をしている間に私がAを、NOSSさんがBを読んでいました。適当にWAとREを投げた後にAをAC。Bの問題文が不明瞭っぽかったので確認をかねてClarを投げました。NOSSさんがBを通してる間に私とnicklawさんでDを考察してました。BのAC後に考察内容をNOSSさんに投げると脳内ACできたので必要なライブラリを探しました。が、ライブラリはJavaとC++が混ざっていてやばかったので3人で爆笑してました（Dは通せませんでした）（ちなみに今でもライブラリは放置されています・・・）

その後

チーム紹介が辞書順の逆向きになり、我らがYokohama National Universityが先頭になって驚き戸惑っていました。国内に英語表記で辞書順で後になる大学なくない？
家に帰ってからABC145に参加し、青→黄になれました。やったね
色変エントリ

mhrbさんのAtCoder Beginner Contest 145での成績：41位
パフォーマンス：2400相当
レーティング：1984→2033 (+49) :)
Highestを更新し、初段になりました！#AtCoder https://t.co/AWftmZlBR2

— まほろば (@mhrb_minase) 2019年11月16日

2日目

コンテスト

開始直前に逆こどふぉ5分前倒しが発生して焦りました。nicklawさんに環境構築をしてもらっている間に私がA、NOSSさんがBを読みました。Aは書いていれば解けるタイプの問題だなあと思いつつ、極度の緊張とUS配列のキーボードに苦しめられ20分強かけてACして疲れ切ってしまうやつをしました（チームメイトのみなさんごめんなさい）。
NOSSさんがBを書いて通している間にnicklawさんと解けそうな問題を探していました。私はFが生えそうで生えてないやつを繰り返してる間に（ちなみにこの問題は難問だったらしい）NOSSさんとnicklawさんでHを通してくれていました。
順位表を見ながらE, G, I, Cあたりに絞りつつ考えていると、私にE問のアイデアが降ってきました。これをNOSSさんとnicklawさんに話して、話し合いながら最後まで解法を詰めることができました。ここで私がトイレに行って帰ってきたらNOSSさんが実装を始めてくれていました。私はNOSSさんの後ろでおにぎりを貪りつつバグを指摘するやつをして、サンプル含めて1発で通すことができました。
その後は数時間考察を続けて椅子を温めつつ虚無を生やし、4完でコンテストが終了しました。

チームEldoradoは4完23位でした

— まほろば (@mhrb_minase) 2019年11月17日

ぱーてぃー

某G社の問題をひたすら考えていたら終わっていました。
春休みの合宿の開催が決まりました（前回の記事）

3日目

2限と4限の授業に出席し、その後競技プログラミング部の活動を行いました。

感想

まずはアジア地区大会に出場し、戦うという貴重な体験ができたのがとてもよかったです。国内予選はギリギリで通過した感があったのですが、アジアではチームの持てる力を出し切れたのではないかなと思っています。その意味では成長を感じられて、私的にはとてもいい大会にすることができたと思っています。

来年に向けて、横国大のチームが予選を勝ち上がるため、自分が迫ってくる学内のライバルに負けないようにするため、精進の日々を過ごしていきたいと思います。

最後に

一緒に戦ってくれたチームメイトの2人、またコーチを務めてくださった方、練習の協力をしてくださったOBの方、弊部の部員の方々、私達を支えてくださってありがとうございました。また、コンテスト運営に携わっている方々には感謝しかありません。この場を借りてお礼申し上げます。ありがとうございました。

AtCoder黄色になりました

起きたら黄色になってました！ pic.twitter.com/f6KMCqxPEy

— まほろば (@mhrb_minase) 2019年11月16日

AtCoder Beginner Contest 145でレートが2033と2000を突破し、黄色になりました。53分41秒で全完での色変でした。初めてのコンテストに出てから1年半とちょっとといった頃合いです。

青になったときの記事はこちらです。

黄色になるまで何をしたか

停滞と微増

振り返ってみて、青から黄色になるまでに何をしたのかを考えたのですが、あまり何もしていないのでは・・・？ということに気づいてしまいました（）少なくとも青になってからすぐの時期や、ICPC国内予選を危なかったとはいえ通過した直後の時期は浮かれていて、コンテストに出たりはしたのですがまともに精進してませんでしたね・・・おかげでレートも行ったり来たりでした。レートの停滞を嫌でも突きつけられていた頃には気持ちの面でももう自分の実力は頭打ちなのではないかと、ネガティブな感情や思考に陥ったりもしていました。9月中旬のJAG夏合宿では自信をへし折られました・・・

転機

そんな中で、9月末か10月の頭頃にAtCoder ProblemsでStreak Rankingが追加され、それを機にStreakを伸ばしてみようというチャレンジを始めました。忙しい日は残っている虚無埋めを、そうでない日はRecommendationsのEasyに表示されたものから順に埋め始めました（執筆時点でLongest Streak更新中です）。

これの効果か、また、ICPCアジア横浜大会に向けてのチームでの練習の成果も相まってかAGCを避けるようにしてからかレートが下がることがなくなりました。また、ABCでは、D問やE問では大小含めて事故もなく、F問も少なくとも全くわからないという状態がなくなり、体感的にも調子が良くなっていました。色変直前の数回では本当に調子がよく、1900の壁を破ってからは割とすんなりと伸ばせたと思います。前にLongest Streakを出したときも調子が良かった気がするので、やはり毎日とまではいかなくても、また実力よりは易しめの問題でも意識して継続的に問題を解くことが重要なのかなと思っています。これからも実力を伸ばせるよう努めていきます。

さいごに

競プロ未経験の私を育ててくださった弊部のみなさん、一方的にライバル認定させていただいていたみなさん、ここまで引き上げていただきありがとうございます。この場を借りてお礼申し上げます。

これにて、色変エントリを締めたいと思います。最後まで読んでくださりありがとうございました。

ベルマンフォード法について ～負閉路の扱い～

グラフの単一始点最短経路問題を解くアルゴリズムとして、ベルマンフォード法が知られている。ダイクストラ法と比較すると、計算量を犠牲にして、コストが負の辺にも対応させたというような格好になっている。コストが負の辺は、単にコストが負というだけならあまり厄介ではないのだが、グラフにコストの総和が負である閉路（以下負閉路）を存在せしめるときに厄介な存在になる。この扱いについて軽くまとめる。

ベルマンフォード法とは

まず、簡単にベルマンフォード法についての説明をする。ベルマンフォード法は、辺を1本ずつ見て、この辺を使ったときに始点から辺の終点へのコストをより小さくできるかを確認していくアルゴリズムである。これをコストの更新が完了するまで繰り返すことで、始点からの最小コストを求めることができる。負閉路に関して、以下の4つのケースが考えられる。

Case 1 負閉路が存在しない場合

これは更新がなくなるまでループを回せばよい。蟻本95ページの中程に載っている実装で十分である。

Case2 負閉路が存在する可能性があり、それを検出したい場合

負閉路が存在するとき、更新がなくなるまでループを回そうとすると、いつまでも更新が止まらなそうである（実際はオーバーフローで止まるかも・・・？）。なので、工夫が必要である。負閉路が存在しないとき、任意の頂点から他の任意の頂点への最短路に含まれる辺の数は、頂点数をVとして高々V-1である。したがって、コストを格納する配列を0で初期化し、ループ回数をカウントし、V回目の更新が起きるかどうかを調べればよい。蟻本95ページ～96ページにかけて掲載されている実装で十分である。

Case3 始点から到達可能な負閉路が存在する可能性があり、それを検出したい場合

始点から到達可能な負閉路が存在するかどうか調べたいときは、コストを格納する配列を始点以外は十分大きい数で初期化しておくとよい。これでV回目の更新が起こるかどうかを調べる。蟻本95ページをぐりぐり読み込むと、中程に載っている実装にV回目の更新が起こるかどうかの判定を加えるだけで実装できることがわかる。

Case4 始点から到達可能であり、終点へ到達可能な閉路がある可能性があり、それを検出したい場合

この記事を書いた理由はこれを書きたかったからである。蟻本にも載っていないし、私のgoogling力が低いのか記事があまり見当たらない（あったら教えてください）（個々の問題に対しての記事ならいくつか存在を確認している）。
このような負閉路は

• 始点から到達可能である
• 負閉路中のいずれかの頂点から終点へ到達可能である

という2つの条件を満たす。これを検出するにはどうすればよいか。始点から到達可能な負閉路はCase3で述べたとおり、V回目の更新が起こるかどうかを調べればよい。そこから特定の終点への最短路に含まれる辺の数は高々V-1本であるため、全体としてはV回目から2V回目までのループ中に終点の更新が起こるかどうかを調べればよさそうである。しかし、これは間違いである。というのも、以下の図のようなグラフを考えるとわかる。

頂点1を始点、頂点5を終点とする。頂点数は5であるから、10回ループを回すことになる。1回目のループで頂点5の最小コストは-10000000となる。2→3→4→2は重みの総和が-1の負閉路であるが、この負閉路を10回通るとその重みの総和は-10である。これでは到底頂点5の更新が起こり得ず、失敗してしまう。
解決する方法は3つ考えられる。

• 負閉路の伝播専用の配列を作る
• 終点へ到達可能な頂点およびそのような頂点のみを結ぶ辺を予め調べ、Case3に帰着する
• V回目以降の更新ではその頂点のコストを十分小さい値にして、V回目から2V回目までのループ中に終点の更新が起こるかどうか調べる

1つ目の方法の解説はここでは省略する。また、2つ目はCase3を参照すればよいため、3つ目についてのみ述べる。V回目の更新である頂点のコストを十分小さい値にしたとする。V回目の更新が起こったため、その頂点へは始点から到達可能な負閉路から到達可能である。その頂点から到達可能な頂点のコストは、以降のV-1回の更新の間に十分小さい値に更新されるはずである。ここで終点の更新が起こる場合は、先ほどの負閉路から終点へ到達可能である。よって、この方法で条件を満たす閉路を調べることができる。実装は以下の通りである。
GitHub - https://github.com/mhrb-minase/competitive_programming/blob/master/Graph/bellman_ford.cpp

#include<vector>
#include<algorithm>
using namespace std;

// 辺を表す構造体
struct edge{
    int from, to;
    long long cost;
};

// v:=頂点数 es:=辺の集合 cost:=始点からの最短経路のコストを格納する配列
// s:=始点(指定しなければ頂点0) g:=終点(指定しなければ頂点v-1)
// 始点から到達可能で、かつ終点へ到達可能な負閉路が検出された場合falseを、それ以外の場合trueを返す
bool bellman_ford(int v, const vector<edge>& es, vector<long long>& cost, int s = 0, int g = -1){
    if(g == -1){
        g = v - 1;
    }

    constexpr long long INF = 1LL << 61;

    cost.assign(v, INF);
    cost[s] = 0;

    for(int i = 0 ; i < v * 2 ; ++i){
        for(auto& e : es){
            if(cost[e.from] < INF && cost[e.from] + e.cost < cost[e.to]){
                if(i >= v - 1 && e.to == g){
                    return false;
                }else if(i >= v - 1){
                    cost[e.to] = -INF;
                }else{
                    cost[e.to] = cost[e.from] + e.cost;
                }
            }
        }
    }

    return true;
}

正直1つ目の方法や2つ目の方法で十分な気がするが、既存のライブラリに少し手を加えるだけでできるということに3つ目の方法の利点を見出すことにしておく。

Case 4の例題（ネタバレ注意）

• ABC061 D Score Attack
• ABC137 E Coins Respawn

ABC128 E Roadwork

問題ページ

解法

人々は整数時刻に座標を出発し、速度で正の方向に歩き続けます。よって、時刻から時刻まで座標を通行止めにするということは、時刻に出発した人は座標で通行止めに当たるということになります。人々が歩いている途中に通行止めに当たった場合はそこで歩くのをやめるので、出発する時刻を被覆する区間のうち最も小さいまで歩き続けるということになります（そのような区間がなければ無限に歩き続けます）。これは遅延評価セグメント木を使えば解くことができます。時刻はそのままでは使えないので座標圧縮をしますが、このとき工事関連の時刻だけではなく、人々が出発する時刻もまとめて座圧すると実装が楽になります。セグ木の更新順は、各クエリでは最小のを求めたいのでの大きい順に更新します。以下の実装では区間取得を行うセグ木を用いていますが、この問題では一点取得に対応していれば十分です。

実装

提出コード - https://atcoder.jp/contests/abc128/submissions/6933093
work:=第一成分が、第二成分の第一成分が、第二成分の第二成分が

#include<iostream>
#include<vector>
#include<limits>
#include<unordered_map>
#include<algorithm>
#include<utility>
using namespace std;

using work = pair<int, pair<int, int> >;

constexpr int INF = 1 << 30;

// 区間更新区間min
template<class T>
class SegmentTree{
    int n;
    vector<T> node, upd;
    vector<bool> flag;

    void evaluate(int k, int l, int r){
        if(flag[k]){
            node[k] = upd[k];
            flag[k] = false;
            if(r - l > 1){
                upd[k * 2 + 1] = upd[k];
                flag[k * 2 + 1] = true;
                upd[k * 2 + 2] = upd[k];
                flag[k * 2 + 2] = true;
            }
        }
        return;
    }

    void update(int a, int b, int k, int l, int r, T x){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            upd[k] = x;
            flag[k] = true;
            evaluate(k, l, r);
            return;
        }

        update(a, b, k * 2 + 1, l, (l + r) / 2, x);
        update(a, b, k * 2 + 2, (l + r) / 2, r, x);

        node[k] = min(node[k * 2 + 1], node[k * 2 + 2]);

        return;
    }

    T get(int a, int b, int k, int l, int r){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return numeric_limits<T>::max();
        }
        if(a <= l && r <= b){
            return node[k];
        }

        T vl = get(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = get(a, b, k * 2 + 2, (l + r) / 2, r);

        return min(vl, vr);
    }

public:
    // 要素数または配列でコンストラクト
    SegmentTree(int siz = 0){
        init(siz);
    }

    SegmentTree(const vector<T> v){
        build(v);
    }

    // 指定された要素数で初期化
    void init(int siz){
        n = 1;
        while(n < siz){
            n <<= 1;
        }

        node.resize(n * 2 - 1);
        fill(node.begin(), node.end(), numeric_limits<T>::max());

        upd.resize(n * 2 - 1);

        flag.resize(n * 2 - 1);
        fill(flag.begin(), flag.end(), false);

        return;
    }

    // 指定された配列で初期化
    void build(const vector<T> v){
        init((int)v.size());

        for(int i = 0, i_len = (int)v.size() ; i < i_len ; ++i){
            node[i + n - 1] = v[i];
        }

        for(int i = n - 2 ; i >= 0 ; --i){
            node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
        }

        return;
    }

    // [a, b)をxに更新
    void update(int a, int b, T x){
        update(a, b, 0, 0, n, x);
        return;
    }

    // [a, b)の取得
    T get(int a, int b){
        return get(a, b, 0, 0, n);
    }
};

template<typename T>
int compress(vector<T> v, unordered_map<T, int> &zip){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0, i_len = (int)v.size() ; i < i_len ; ++i){
        zip[v[i]] = i;
    }
    return (int)v.size();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    vector<int> ti;

    vector<work> v;
    for(int i = 0 ; i < n ; ++i){
        int s, t, x;
        cin >> s >> t >> x;
        v.push_back({x, {s - x, t - x}});
        ti.push_back(s - x);
        ti.push_back(t - x);
    }

    vector<int> query;
    for(int i = 0 ; i < q ; ++i){
        int d;
        cin >> d;
        query.push_back(d);
        ti.push_back(d);
    }

    unordered_map<int, int> zip;
    int m = compress(ti, zip);

    SegmentTree<int> seg(m);

    sort(v.begin(), v.end(), [](work l, work r){ return l.first > r.first; });
    for(int i = 0 ; i < n ; ++i){
        seg.update(zip[v[i].second.first], zip[v[i].second.second], v[i].first);
    }

    for(auto &d : query){
        int ans = seg.get(zip[d], zip[d] + 1);
        if(ans < INF){
            cout << ans << endl;
        }else{
            cout << -1 << endl;
        }
    }

    return 0;
}

ARC024 D バス停

問題ページ

解法

ある列の格子点全てにバス停を置くと、任意のその列を跨いだ左右間の移動が可能となり、かつ総移動距離がマンハッタン距離と等しくなるようにできる。よって、左右独立に考えることができるようになるため、分割統治でこの問題を解くことができる。実際に全ての格子点にバス停を置く必要はなく、バス停がある行にだけ置けば十分である。これをバス停がある列を順に並べた時にちょうど真ん中の列に対して行い、左右それぞれの区域でも同じことを再帰的に行う。これでバス停を置く個数がおよそNlogN個となり、個数の制約をクリアできる。

実装

提出コード - https://atcoder.jp/contests/arc024/submissions/6750348

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
using namespace std;

vector< pair<int, int> > v, ans;
set< pair<int, int> > st;

void solve(int l, int r){
    if(r - l <= 1){
        return;
    }

    int m = (l + r) / 2;
    for(int i = l ; i < r ; ++i){
        if(v[i].first != v[m].first && v[i].second != v[m].second && !st.count({v[m].first, v[i].second})){
            ans.emplace_back(v[m].first, v[i].second);
            st.insert(ans.back());
        }
    }

    solve(l, m);
    solve(m + 1, r);

    return;
}

int main(){
    int n;
    cin >> n;

    for(int i = 0 ; i < n ; ++i){
        int x, y;
        cin >> x >> y;
        v.emplace_back(x, y);
        st.insert(v.back());
    }
    sort(v.begin(), v.end());

    solve(0, n);

    cout << ans.size() << endl;
    for(auto x : ans){
        cout << x.first << " " << x.second << endl;
    }

    return 0;
}

ARC036 D 偶数メートル

問題ページ

解法

2つの街が直接偶数メートルで繋がっているか、2つの街の両方から行き来できる奇数長の閉路があれば、またその時に限りクエリに対する出力はYESとなる。これは、重み付き（ポテンシャル付き）Union-Find木を使うと調べることができる。道路を繋ぐとき、もともと繋がっていない場合はそのまま繋ぐ。繋がっていた場合、その間の距離と新しい道路の距離の和が奇数であれば、奇数長の閉路ができることになる。奇数長の閉路があるかどうかをbool配列で管理しておくことによって、この問題を解くことができる。

実装

提出コード - https://atcoder.jp/contests/arc036/submissions/6435962
重み付きUF - https://github.com/mhrb-minase/competitive_programming/blob/master/DataStructure/UnionFind.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;

class UnionFind{
    vector<int> par;
    vector<long long> wei;
    int groupCount;

public:
    UnionFind(int n = 0){
        init(n);
    }

    void init(int n = 0){
        par.resize(n);
        fill(par.begin(), par.end(), -1);

        wei.resize(n);
        fill(wei.begin(), wei.end(), 0LL);

        groupCount = n;

        return;
    }

    int root(int x){
        if(par[x] < 0){
            return x;
        }
        int r = root(par[x]);
        wei[x] += wei[par[x]];
        return par[x] = r;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int size(int x){
        return -par[root(x)];
    }

    long long weight(int x){
        root(x);
        return wei[x];
    }

    long long diff(int x, int y){
        return weight(y) - weight(x);
    }

    bool unite(int x, int y, long long w = 0){
        w += weight(x) - weight(y);

        x = root(x);
        y = root(y);

        if(x == y){
            return false;
        }

        if(par[y] < par[x]){
            swap(x, y);
            w = -w;
        }

        par[x] += par[y];
        par[y] = x;
        wei[y] = w;
        --groupCount;

        return true;
    }

    int size(void){
        return groupCount;
    }
};

int main(){
    int n, q;
    cin >> n >> q;

    UnionFind uf(n);
    vector<bool> v(n, false);

    while(q--){
        int w, x, y;
        long long z;
        cin >> w >> x >> y >> z;
        --x;
        --y;
        if(w == 1){
            if(uf.same(x, y)){
                if(abs(uf.diff(x, y)) % 2LL != z % 2LL){
                    v[uf.root(x)] = true;
                }
            }else{
                bool flag = v[uf.root(x)] || v[uf.root(y)];
                uf.unite(x, y, z);
                v[uf.root(x)] = flag;
            }
        }else{
            if(uf.same(x, y) && (abs(uf.diff(x, y)) % 2LL == 0LL || v[uf.root(x)])){
                cout << "YES" << endl;
            }else{
                cout << "NO" << endl;
            }
        }
    }

    return 0;
}

JOI 2019 予選 (AOJ 0656) イルミネーション

問題ページ

解法

番目の木までを見たときの美しさの最大値とする。すると遷移は、その木を使わないときとなる。木を使う場合、を満たすに対して高々1本しか木を使えないという制限がある。よって、木を使う場合はこれを満たすものの中で最大のの次に遷移する。これは遅延評価セグ木を用いて管理すればよい。セグ木をが小さい順に更新すれば目的を達成できる。

実装

提出コード - https://onlinejudge.u-aizu.ac.jp/recent_judges/0656/judge/3755513/mhrb_minase/C++14

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
using namespace std;

template<typename T>
bool chmax(T &a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T &a, T b){
    if(b < a){
        a = b;
        return true;
    }
    return false;
}

template<class T>
class SegmentTree{
    int n;
    vector<T> node, upd;
    vector<bool> flag;

    void evaluate(int k, int l, int r){
        if(flag[k]){
            node[k] = upd[k];
            flag[k] = false;
            if(r - l > 1){
                upd[k * 2 + 1] = upd[k];
                flag[k * 2 + 1] = true;
                upd[k * 2 + 2] = upd[k];
                flag[k * 2 + 2] = true;
            }
        }
        return;
    }

    void update(int a, int b, int k, int l, int r, T x){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            upd[k] = x;
            flag[k] = true;
            evaluate(k, l, r);
            return;
        }

        update(a, b, k * 2 + 1, l, (l + r) / 2, x);
        update(a, b, k * 2 + 2, (l + r) / 2, r, x);

        node[k] = max(node[k * 2 + 1], node[k * 2 + 2]);

        return;
    }

    T get(int a, int b, int k, int l, int r){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return numeric_limits<T>::min();
        }
        if(a <= l && r <= b){
            return node[k];
        }

        T vl = get(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = get(a, b, k * 2 + 2, (l + r) / 2, r);

        return max(vl, vr);
    }

public:
    SegmentTree(int siz = 0){
        init(siz);
    }

    SegmentTree(const vector<T> v){
        build(v);
    }

    void init(int siz){
        n = 1;
        while(n < siz){
            n <<= 1;
        }

        node.resize(n * 2 - 1);
        fill(node.begin(), node.end(), T(0));

        upd.resize(n * 2 - 1);

        flag.resize(n * 2 - 1);
        fill(flag.begin(), flag.end(), false);

        return;
    }

    void build(const vector<T> v){
        init((int)v.size());

        for(int i = 0, i_len = (int)v.size() ; i < i_len ; ++i){
            node[i + n - 1] = v[i];
        }

        for(int i = n - 2 ; i >= 0 ; --i){
            node[i] = max(node[i * 2 + 1], node[i * 2 + 2]);
        }

        return;
    }

    void update(int a, int b, T x){
        update(a, b, 0, 0, n, x);
        return;
    }

    T get(int a, int b){
        return get(a, b, 0, 0, n);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n);
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
    }

    vector<int> l(m), r(m), id(m);
    for(int i = 0 ; i < m ; ++i){
        cin >> l[i] >> r[i];
        --l[i];
        --r[i];
        id[i] = i;
    }

    sort(id.begin(), id.end(), [&](int i, int j){ return r[i] < r[j]; });

    SegmentTree<int> seg(n);
    for(int i = 0 ; i < n ; ++i){
        seg.update(i, i + 1, i + 1);
    }

    for(int i = 0 ; i < m ; ++i){
        seg.update(l[id[i]], r[id[i]] + 1, r[id[i]] + 1);
    }

    vector<long long> dp(n + 1);
    for(int i = 0 ; i < n ; ++i){
        chmax(dp[i + 1], dp[i]);
        chmax(dp[seg.get(i, i + 1)], dp[i] + a[i]);
    }

    cout << dp[n] << endl;

    return 0;
}