Submission #973710

#	Time	Username	Problem	Language	Result	Execution time	Memory
973710		RaresFelix	Food Court (JOI21_foodcourt)	C++17	100 / 100	436 ms	57640 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define int ll
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<ll, ll>;

struct ura1 {
    int n;
    vll V, Mi, Lz;
    ura1(int N) : n(N), V(N, 0), Mi(4 * N, 0), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        if(!Lz[u]) return;
        Mi[u] += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int l, int r, int v, int u, int s, int d) {
        prop(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            Lz[u] += v;
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
    }

    const ll INF = 1e18;

    int query(int l, int r, int u, int s, int d) {
        prop(u, s, d);
        if(r < s || d < l) return INF;
        if(l <= s && d <= r) return Mi[u];
        return min(query(l, r, u << 1, s, (s + d) >> 1), 
            query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
    }

    void update(int p, int v) {
        ///update pe pozitie
        update(p, n - 1, v - V[p], 1, 0, n - 1);
        V[p] = v;
    }

    int query(int p) {
        if(p == -1) return 0;
        return query(p, p, 1, 0, n - 1) - min(query(0, p - 1, 1, 0, n - 1), 0ll);
    }
};

struct ura2 {
    ll n;
    vll S;
    ura2(int N) : n(N), S(4 * N) {}

    void update(int p, int v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
            S[u] = v;
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        S[u] = S[u << 1] + S[u << 1 | 1];
    }

    int querys(int l, int r, int u, int s, int d) {
        if(d < l || r < s) {
            return 0;
        }
        if(l <= s && d <= r) return S[u];
        return querys(l, r, u << 1, s, (s + d) >> 1)
            + querys(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
    }

    int queryp(int nr, int u, int s, int d) {
        if(s == d) return s;
        if(nr > S[u << 1]) return queryp(nr - S[u << 1], u << 1 | 1, ((s + d) >> 1) + 1, d);
        return queryp(nr, u << 1, s, (s + d) >> 1);
    }

    void update(int p, int v) { ///update pe pozitie
        update(p, v, 1, 0, n - 1);
    }
    int sum(int p) { return querys(0, p, 1, 0, n - 1); }
    int query(int nr) { /// va returna pozitia celul a al nr-lea element
        return queryp(nr, 1, 0, n - 1);
    }
};

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vi V1, V2, C2;
    vector<ii> UpV1, UpV2; /// toggle-uri pe timp
    struct query {
        int poz, id, ultV1, ultV2;
    };
    vector<vector<query> > Q(n);
    int nr3 = 0;
    for (int i = 0; i < q; ++i) {
        int tip;
        cin >> tip;
        if (tip == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            --l; --r;
            UpV1.push_back({l, V1.size()});
            UpV1.push_back({r + 1, V1.size()});
            UpV2.push_back({l, V2.size()});
            UpV2.push_back({r + 1, V2.size()});

            V1.push_back(k);
            V2.push_back(k);
            C2.push_back(c);
        } else if (tip == 2) {
            int l, r, k;
            cin >> l >> r >> k; 
            --l; --r;
            UpV1.push_back({l, V1.size()});
            UpV1.push_back({r + 1, V1.size()});
            V1.push_back(-k);
        } else {
            int a, b;
            cin >> a >> b;
            --a;
            Q[a].push_back({b, nr3, int(V1.size()) - 1, int(V2.size()) - 1});
            ++nr3;
        }
    }
    sort(UpV1.begin(), UpV1.end());
    sort(UpV2.begin(), UpV2.end());

    int p1 = 0, p2 = 0;
    vi Re(nr3);

    ura1 Sol1(V1.size());
    vi on1(V1.size(), 0);
    ura2 Sol2(V2.size());
    vi on2(V2.size(), 0);

    for(int i = 0; i < n; ++i) {
        while(p1 < UpV1.size() && UpV1[p1].first <= i) {
            //toggle it
            int v = UpV1[p1].second;
            if(!on1[v]) Sol1.update(v, V1[v]);
            else Sol1.update(v, 0);
            on1[v] ^= 1;
            ++p1;
        }

        while(p2 < UpV2.size() && UpV2[p2].first <= i) {
            //toggle it
            int v = UpV2[p2].second;
            if(!on2[v]) Sol2.update(v, V2[v]);
            else Sol2.update(v, 0);
            on2[v] ^= 1;
            ++p2;
        }

        for(auto q : Q[i]) {
            ll nrsuf = Sol1.query(q.ultV1), nrtot = Sol2.sum(q.ultV2);
            ll b = q.poz + nrtot - nrsuf;
            if(b > nrtot) {
                Re[q.id] = 0;
            } else {
                Re[q.id] = C2[Sol2.query(b)];
            }
        }
    }
    for(auto it : Re) cout << it << "\n";
    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:155:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         while(p1 < UpV1.size() && UpV1[p1].first <= i) {
      |               ~~~^~~~~~~~~~~~~
foodcourt.cpp:164:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         while(p2 < UpV2.size() && UpV2[p2].first <= i) {
      |               ~~~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11