Submission #976440

#	Time	Username	Problem	Language	Result	Execution time	Memory
976440		underwaterkillerwhale	Food Court (JOI21_foodcourt)	C++17	24 / 100	159 ms	191828 KiB

foodcourt

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 5e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e18 + 7;
const int BASE = 137;

struct Data3 {
    ll idx, pos, id;
};

int n, m, Q;
int color[N];
vector<pair<ll,int>> q1[N];
vector<Data3> q3[N];

struct Segment_Tree_Beats {
    int Range;
    struct Node {
        ll lz, mn1, mn2, mnc, sum;
        Node (ll lz = 0, ll mn1 = 0, ll mn2 = INF, ll mnc = 0, ll sum = 0) : lz(lz), mn1(mn1), mn2(mn2), mnc(mnc), sum(sum) {};
    };
    Node st[N << 2];

    void init (int n) {
        Range = n;
    }

    void Merge (Node &cur, Node &left, Node &right){
        cur.sum = left.sum + right.sum;
        if (left.mn1 <= right.mn1) {
            cur.mn1 = left.mn1, cur.mnc = left.mnc;
            if (left.mn1 == right.mn1) cur.mnc += right.mnc, cur.mn2 = min(left.mn2, right.mn2);
            else cur.mn2 = min(left.mn2, right.mn1);
        }
        else {
            cur.mn1 = right.mn1, cur.mnc = right.mnc;
            cur.mn2 = min(left.mn1, right.mn2);
        }
    }

    void build (int id, int l, int r) {
        if (l == r) {
            st[id].mn1 = 0;
            st[id].mn2 = INF;
            st[id].mnc = 1;
            st[id].sum = 0;
            return;
        }
        int mid = l + r >> 1;
        build (id << 1, l, mid);
        build (id << 1 | 1, mid + 1, r);
        Merge (st[id], st[id << 1], st[id << 1 | 1]);
    }
    void down (int id, int l, int r) {
        int mid = l + r >> 1;
        int left = (id << 1), right = (id << 1 | 1);
        st[left].sum += st[id].lz * (mid - l + 1);
        st[right].sum += st[id].lz * (r - mid);
        rep (i, left, right) {
            st[i].mn1 += st[id].lz;
            st[i].lz += st[id].lz;
            if (st[i].mn1 < st[id].mn1) {
                st[i].sum += 1LL * (st[id].mn1 - st[i].mn1) * st[i].mnc;
                st[i].mn1 = st[id].mn1;
            }
            if (st[i].mn2 != INF) st[i].mn2 += st[id].lz;
        }
        st[id].lz = 0;
    }

    void update1 (int id, int l, int r, int u, int v, ll val) {
        if (l > v  || r < u) return;
        if (l >= u && r <= v) {
            st[id].sum += 1LL * (r - l + 1) * val;
            st[id].lz += val;
            st[id].mn1 += val;
            if(st[id].mn2 != INF) st[id].mn2 += val;
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        update1 (id << 1, l, mid, u, v, val);
        update1 (id << 1 | 1, mid + 1, r, u, v, val);
        Merge (st[id], st[id << 1], st[id << 1 | 1]);
    }

    void update2 (int id, int l, int r, int u, int v, ll val) {
        if (l > v  || r < u || st[id].mn1 >= val) return;
        if (l >= u && r <= v && st[id].mn2 > val) {
            st[id].sum += 1LL * (val - st[id].mn1) * st[id].mnc;
            st[id].mn1 = val;
//            cout << id <<" "<<l<<" "<<r<<" "<<st[id].sum<<" "<<st[id].mn1<<" "<<st[id].mnc<<"hihih\n";
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        update2 (id << 1, l, mid, u, v, val);
        update2 (id << 1 | 1, mid + 1, r, u, v, val);
        Merge (st[id], st[id << 1], st[id << 1 | 1]);
    }

    ll get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v)
            return st[id].sum;
        int mid = l + r >> 1;
        down(id, l, r);
        return get (id << 1, l, mid, u, v) + get (id << 1 | 1, mid + 1, r, u, v);
    }

    void update1 (int u, int v, ll val) {
        update1 (1, 1, Range, u, v, val);
    }
    void update2 (int u, int v, ll val) {
        update2 (1, 1, Range, u, v, val);
    }
    ll get (int u, int v) {
        return get (1, 1, Range, u, v);
    }
}ST, Tot;

struct Fenwick_Tree {
    int Range;
    ll fen[N];
    void init (int n) { Range = n; }
    void update (int pos, ll val) {
        for (; pos <= Range; pos += pos & -pos) fen[pos] += val;
    }
    ll get (int pos) {
        ll res = 0;
        for (; pos > 0; pos -= pos & -pos) res += fen[pos];
        return res;
    }
}BIT;

void solution() {
    cin >> n >> m >> Q;
    ST.init(n);
    ST.build(1, 1, n);
    Tot.init(n);
    int numq3 = 0;
//    ST.update1 (3, 3, 2);
//    ST.update1 (3, 3, -3);
//    ST.update2 (3, 3, 0);
//    ST.update1 (3, 3, 2);
//    cout << ST.get (3, 3) <<"\n";
//    return;
    rep (i, 1, Q) {
        int typ;
        cin >> typ;
        if (typ == 1) {
            ll L, R, C, K;
            cin >> L >> R >> C >> K;
            color[i] = C;
            q1[L].push_back({K, i});
            q1[R + 1].push_back({-K, i});
            ST.update1 (L, R, K);
            Tot.update1 (L, R, K);
        }
        else if (typ == 2) {
            ll L, R, K;
            cin >> L >> R >> K;
            ST.update1 (L, R, -K);
            ST.update2 (L, R, 0);
//            cout <<i<<" typ2 :"<<ST.get(3, 3)<<"\n";
        }
        else {
            int pos, X;
            cin >> pos >> X;
            int idx = Tot.get (pos, pos) - ST.get (pos, pos) + X;
//            cout << i<<": "<<idx<<" "<<Tot.get (pos, pos)<<" "<<ST.get (pos, pos) <<"\n";
            q3[pos].push_back({idx, numq3++, i});
        }
    }
    vector<int> Ans(numq3);
    BIT.init(Q + 1);
    rep (i, 1, n) {
        iter (&id, q1[i]) {
            BIT.update (id.se, id.fs);
        }
        iter (&id, q3[i]) {
            int pos; {
                int lf = 1, rt = id.id;
                while (lf < rt) {
                    int mid = lf + rt >> 1;
                    if (BIT.get(mid) >= id.idx) rt = mid;
                    else lf = mid + 1;
                }
                pos = lf;
            }
//            cout << id.id<<":"<<pos<<" "<<BIT.get(pos) <<"\n";
            if (BIT.get (pos) >= id.idx) Ans[id.pos] = color[pos];
            else Ans[id.pos] = 0;
        }
    }
    iter (&id, Ans) cout << id <<"\n";
}



#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

Compilation message (stderr)

foodcourt.cpp: In member function 'void Segment_Tree_Beats::build(int, int, int)':
foodcourt.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::down(int, int, int)':
foodcourt.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::update1(int, int, int, int, int, long long int)':
foodcourt.cpp:99:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::update2(int, int, int, int, int, long long int)':
foodcourt.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'long long int Segment_Tree_Beats::get(int, int, int, int, int)':
foodcourt.cpp:125:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'void solution()':
foodcourt.cpp:204:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  204 |                     int mid = lf + rt >> 1;
      |                               ~~~^~~~

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