Submission #124622

#	Time	Username	Problem	Language	Result	Execution time	Memory
124622		choikiwon	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	4251 ms	32460 KiB

arranging_tickets

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 200010;

int N, M;
ll cnt[MN];
vector<pair<ll, int> > stk;
vector<pii> V[MN];

struct BIT {
    vector<ll> tree, lazy;
    void init() {
        tree = vector<ll>(4 * N);
        lazy = vector<ll>(4 * N, 0);
        build(0, N - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = cnt[l];
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n] += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1] += lazy[n];
            lazy[2*n + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, ll d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    ll quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        ll L = quer(a, b, l, m, 2*n);
        ll R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit;

struct Info {
    int a, b, c;
    bool operator <(const Info &i) const {
        return b < i.b;
    }
};

priority_queue<Info> pq;

bool check(ll bound) {
    bit.init();
    while(!pq.empty()) pq.pop();

    int pos = 0;
    for(int i = 0; i < stk.size(); i++) {
        while(pos <= stk[i].second) {
            for(int j = 0; j < V[pos].size(); j++) {
                pq.push({ pos, V[pos][j].first, V[pos][j].second });
            }
            pos++;
        }
        int x = stk[i].second;

        ll t = bit.quer(x, x, 0, N - 1, 1);
        ll d = bit.tree[1];
        ll need = max(0LL, (t + d - 2 * bound + 1) / 2);

        while(need && !pq.empty()) {
            Info t = pq.top(); pq.pop();

            ll mn = min(need, 1LL * t.c);
            need -= mn;
            t.c -= mn;
            if(t.c) pq.push(t);

            bit.upd(0, N - 1, mn, 0, N - 1, 1);
            bit.upd(t.a, t.b, -2 * mn, 0, N - 1, 1);
        }
        if(need) return false;
        if(bit.tree[1] <= bound) return true;
    }
    return false;
}

int main() {
    scanf("%d %d", &N, &M);

    ll sum = 0;
    for(int i = 0; i < M; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        if(a > b) swap(a, b);
        b--;

        cnt[a] += c;
        cnt[b + 1] -= c;
        V[a].push_back(pii(b, c));
        sum += c;
    }
    for(int i = 1; i < N; i++) cnt[i] += cnt[i - 1];

    for(int i = N - 1; i >= 0; i--) {
        while(!stk.empty() && stk.back().first <= cnt[i]) stk.pop_back();
        stk.push_back({cnt[i], i});
    }
    reverse(stk.begin(), stk.end());

    ll s = 0, e = sum, p = -1;
    while(s <= e) {
        ll m = (s + e)>>1;

        if(check(m)) {
            p = m;
            e = m - 1;
        }
        else s = m + 1;
    }
    printf("%lld", p);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
arranging_tickets.cpp:113:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b, c; scanf("%d %d %d", &a, &b, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15