Submission #44487

#	Time	Username	Problem	Language	Result	Execution time	Memory
44487		choikiwon	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	2 ms	380 KiB

arranging_tickets

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

typedef long long ll;

int N, M;
struct Info {
    int a, b, c, id;
    bool operator <(const Info &i) const {
        return id < i.id;
    }
};
set<Info> st;
ll arr[200010];

struct node {
    ll mx1, mx2, l, r;
};

node mrg(node &a, node &b) {
    node ret;
    if(abs(a.mx1 - b.mx1) < 2) {
        ret.mx1 = a.mx1;
        ret.mx2 = max(a.mx2, b.mx2);
        ret.l = min(a.l, b.l);
        ret.r = max(a.r, b.r);
    }
    else if(a.mx1 > b.mx1) {
        ret.mx1 = a.mx1;
        ret.mx2 = max(a.mx2, b.mx1);
        ret.l = a.l;
        ret.r = a.r;
    }
    else {
        ret.mx1 = b.mx1;
        ret.mx2 = max(a.mx1, b.mx2);
        ret.l = b.l;
        ret.r = b.r;
    }
    return ret;
}

struct BIT {
    vector<node> tree;
    vector<ll> lazy;
    void init() {
        tree = vector<node>(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] = {arr[l], (ll)-1e18, l, l};
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n].mx1 += lazy[n];
            tree[2*n].mx2 += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1].mx1 += lazy[n];
            tree[2*n + 1].mx2 += 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].mx1 += d;
            tree[n].mx2 += 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] = mrg(tree[2*n], tree[2*n + 1]);
    }
} bit;

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

    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);

        arr[a] += c;
        arr[b] -= c;
        st.insert({ a, b, c, i });
    }

    ll ans = arr[0];
    for(int i = 1; i < N; i++) {
        arr[i] += arr[i - 1];
        ans = max(ans, arr[i]);
    }

    bit.init();
    while(1) {
        node t = bit.tree[1];

        set<Info>::iterator it;
        while(st.size()) {
            it = st.begin();
            if(!(it->a <= t.l && t.r < it->b)) {
                st.erase(it);
            }
            else break;
        }
        if(!st.size()) break;

        Info tmp = *it;
        st.erase(st.find(tmp));

        if(t.mx1 - t.mx2 <= 2 * tmp.c) {
            bit.upd(tmp.a, tmp.b - 1, -(t.mx1 - t.mx2) / 2 * 2, 0, N - 1, 1);
            tmp.c -= (t.mx1 - t.mx2) / 2;
            ans -= (t.mx1 - t.mx2) / 2;
            st.insert(tmp);
        }
        else {
            bit.upd(tmp.a, tmp.b - 1, -tmp.c * 2, 0, N - 1, 1);
            ans -= tmp.c;
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:89: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:92: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: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15