oj.uz

Submission #976430

# Submission time Handle Problem Language Result Execution time Memory
976430 2024-05-06T14:51:19 Z underwaterkillerwhale Food Court (JOI21_foodcourt) C++17
24 / 100
 164 ms 189116 KB 
#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 {
    int idx, pos, id;
};

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

struct Segment_Tree_Beats {
    int Range;
    struct Node {
        ll lz, mn1, mn2, mnc, sum;
        Node (int lz = 0, int mn1 = 0, ll mn2 = INF, int mnc = 0, int 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 += (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) {
            int 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) {
            int 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

foodcourt.cpp: In member function 'void Segment_Tree_Beats::build(int, int, int)':
foodcourt.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::down(int, int, int)':
foodcourt.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         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:100:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         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:115:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'long long int Segment_Tree_Beats::get(int, int, int, int, int)':
foodcourt.cpp:126:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'void solution()':
foodcourt.cpp:205:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  205 |                     int mid = lf + rt >> 1;
      |                               ~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 183120 KB Output is correct
2 Correct 41 ms 183052 KB Output is correct
3 Correct 36 ms 183116 KB Output is correct
4 Correct 37 ms 183120 KB Output is correct
5 Correct 31 ms 183124 KB Output is correct
6 Correct 31 ms 182992 KB Output is correct
7 Correct 35 ms 183124 KB Output is correct
8 Correct 36 ms 183320 KB Output is correct
9 Correct 33 ms 182988 KB Output is correct
10 Correct 32 ms 183100 KB Output is correct
11 Correct 31 ms 183168 KB Output is correct
12 Correct 32 ms 183104 KB Output is correct
13 Correct 33 ms 182928 KB Output is correct
14 Correct 30 ms 183020 KB Output is correct
15 Correct 37 ms 183120 KB Output is correct
16 Correct 31 ms 183052 KB Output is correct
17 Correct 32 ms 182936 KB Output is correct
18 Correct 31 ms 183136 KB Output is correct
19 Correct 31 ms 183128 KB Output is correct
20 Correct 33 ms 183132 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 183120 KB Output is correct
2 Correct 41 ms 183052 KB Output is correct
3 Correct 36 ms 183116 KB Output is correct
4 Correct 37 ms 183120 KB Output is correct
5 Correct 31 ms 183124 KB Output is correct
6 Correct 31 ms 182992 KB Output is correct
7 Correct 35 ms 183124 KB Output is correct
8 Correct 36 ms 183320 KB Output is correct
9 Correct 33 ms 182988 KB Output is correct
10 Correct 32 ms 183100 KB Output is correct
11 Correct 31 ms 183168 KB Output is correct
12 Correct 32 ms 183104 KB Output is correct
13 Correct 33 ms 182928 KB Output is correct
14 Correct 30 ms 183020 KB Output is correct
15 Correct 37 ms 183120 KB Output is correct
16 Correct 31 ms 183052 KB Output is correct
17 Correct 32 ms 182936 KB Output is correct
18 Correct 31 ms 183136 KB Output is correct
19 Correct 31 ms 183128 KB Output is correct
20 Correct 33 ms 183132 KB Output is correct
21 Incorrect 29 ms 182924 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 187984 KB Output is correct
2 Correct 135 ms 188340 KB Output is correct
3 Correct 130 ms 186448 KB Output is correct
4 Correct 149 ms 188312 KB Output is correct
5 Correct 139 ms 188328 KB Output is correct
6 Correct 140 ms 188440 KB Output is correct
7 Correct 46 ms 186532 KB Output is correct
8 Correct 55 ms 186888 KB Output is correct
9 Correct 127 ms 187984 KB Output is correct
10 Correct 136 ms 188044 KB Output is correct
11 Correct 137 ms 187968 KB Output is correct
12 Correct 135 ms 188044 KB Output is correct
13 Correct 117 ms 187988 KB Output is correct
14 Correct 132 ms 188476 KB Output is correct
15 Correct 153 ms 188616 KB Output is correct
16 Correct 139 ms 188764 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 189116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 183120 KB Output is correct
2 Correct 41 ms 183052 KB Output is correct
3 Correct 36 ms 183116 KB Output is correct
4 Correct 37 ms 183120 KB Output is correct
5 Correct 31 ms 183124 KB Output is correct
6 Correct 31 ms 182992 KB Output is correct
7 Correct 35 ms 183124 KB Output is correct
8 Correct 36 ms 183320 KB Output is correct
9 Correct 33 ms 182988 KB Output is correct
10 Correct 32 ms 183100 KB Output is correct
11 Correct 31 ms 183168 KB Output is correct
12 Correct 32 ms 183104 KB Output is correct
13 Correct 33 ms 182928 KB Output is correct
14 Correct 30 ms 183020 KB Output is correct
15 Correct 37 ms 183120 KB Output is correct
16 Correct 31 ms 183052 KB Output is correct
17 Correct 32 ms 182936 KB Output is correct
18 Correct 31 ms 183136 KB Output is correct
19 Correct 31 ms 183128 KB Output is correct
20 Correct 33 ms 183132 KB Output is correct
21 Correct 136 ms 187984 KB Output is correct
22 Correct 135 ms 188340 KB Output is correct
23 Correct 130 ms 186448 KB Output is correct
24 Correct 149 ms 188312 KB Output is correct
25 Correct 139 ms 188328 KB Output is correct
26 Correct 140 ms 188440 KB Output is correct
27 Correct 46 ms 186532 KB Output is correct
28 Correct 55 ms 186888 KB Output is correct
29 Correct 127 ms 187984 KB Output is correct
30 Correct 136 ms 188044 KB Output is correct
31 Correct 137 ms 187968 KB Output is correct
32 Correct 135 ms 188044 KB Output is correct
33 Correct 117 ms 187988 KB Output is correct
34 Correct 132 ms 188476 KB Output is correct
35 Correct 153 ms 188616 KB Output is correct
36 Correct 139 ms 188764 KB Output is correct
37 Correct 124 ms 187740 KB Output is correct
38 Correct 108 ms 187728 KB Output is correct
39 Correct 43 ms 186444 KB Output is correct
40 Correct 46 ms 186832 KB Output is correct
41 Correct 122 ms 187988 KB Output is correct
42 Correct 143 ms 187984 KB Output is correct
43 Correct 139 ms 187984 KB Output is correct
44 Correct 145 ms 187988 KB Output is correct
45 Correct 129 ms 187864 KB Output is correct
46 Correct 137 ms 187932 KB Output is correct
47 Correct 66 ms 187296 KB Output is correct
48 Correct 113 ms 187476 KB Output is correct
49 Correct 115 ms 186984 KB Output is correct
50 Correct 137 ms 187432 KB Output is correct
51 Correct 152 ms 187988 KB Output is correct
52 Correct 164 ms 188024 KB Output is correct
53 Correct 117 ms 187988 KB Output is correct
54 Correct 140 ms 188756 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 186320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 183120 KB Output is correct
2 Correct 41 ms 183052 KB Output is correct
3 Correct 36 ms 183116 KB Output is correct
4 Correct 37 ms 183120 KB Output is correct
5 Correct 31 ms 183124 KB Output is correct
6 Correct 31 ms 182992 KB Output is correct
7 Correct 35 ms 183124 KB Output is correct
8 Correct 36 ms 183320 KB Output is correct
9 Correct 33 ms 182988 KB Output is correct
10 Correct 32 ms 183100 KB Output is correct
11 Correct 31 ms 183168 KB Output is correct
12 Correct 32 ms 183104 KB Output is correct
13 Correct 33 ms 182928 KB Output is correct
14 Correct 30 ms 183020 KB Output is correct
15 Correct 37 ms 183120 KB Output is correct
16 Correct 31 ms 183052 KB Output is correct
17 Correct 32 ms 182936 KB Output is correct
18 Correct 31 ms 183136 KB Output is correct
19 Correct 31 ms 183128 KB Output is correct
20 Correct 33 ms 183132 KB Output is correct
21 Incorrect 29 ms 182924 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 183120 KB Output is correct
2 Correct 41 ms 183052 KB Output is correct
3 Correct 36 ms 183116 KB Output is correct
4 Correct 37 ms 183120 KB Output is correct
5 Correct 31 ms 183124 KB Output is correct
6 Correct 31 ms 182992 KB Output is correct
7 Correct 35 ms 183124 KB Output is correct
8 Correct 36 ms 183320 KB Output is correct
9 Correct 33 ms 182988 KB Output is correct
10 Correct 32 ms 183100 KB Output is correct
11 Correct 31 ms 183168 KB Output is correct
12 Correct 32 ms 183104 KB Output is correct
13 Correct 33 ms 182928 KB Output is correct
14 Correct 30 ms 183020 KB Output is correct
15 Correct 37 ms 183120 KB Output is correct
16 Correct 31 ms 183052 KB Output is correct
17 Correct 32 ms 182936 KB Output is correct
18 Correct 31 ms 183136 KB Output is correct
19 Correct 31 ms 183128 KB Output is correct
20 Correct 33 ms 183132 KB Output is correct
21 Incorrect 29 ms 182924 KB Output isn't correct
22 Halted 0 ms 0 KB -