oj.uz

Submission #976439

# Submission time Handle Problem Language Result Execution time Memory
976439 2024-05-06T14:54:50 Z underwaterkillerwhale Food Court (JOI21_foodcourt) C++17
24 / 100
 158 ms 191856 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 {
    ll 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 (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

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 32 ms 183388 KB Output is correct
2 Correct 31 ms 183252 KB Output is correct
3 Correct 32 ms 183132 KB Output is correct
4 Correct 32 ms 183024 KB Output is correct
5 Correct 33 ms 183120 KB Output is correct
6 Correct 30 ms 183124 KB Output is correct
7 Correct 31 ms 183072 KB Output is correct
8 Correct 33 ms 183132 KB Output is correct
9 Correct 32 ms 183124 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 32 ms 183120 KB Output is correct
12 Correct 32 ms 183044 KB Output is correct
13 Correct 30 ms 182980 KB Output is correct
14 Correct 31 ms 183132 KB Output is correct
15 Correct 31 ms 183128 KB Output is correct
16 Correct 34 ms 183132 KB Output is correct
17 Correct 32 ms 183120 KB Output is correct
18 Correct 31 ms 183132 KB Output is correct
19 Correct 31 ms 182952 KB Output is correct
20 Correct 32 ms 183132 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 183388 KB Output is correct
2 Correct 31 ms 183252 KB Output is correct
3 Correct 32 ms 183132 KB Output is correct
4 Correct 32 ms 183024 KB Output is correct
5 Correct 33 ms 183120 KB Output is correct
6 Correct 30 ms 183124 KB Output is correct
7 Correct 31 ms 183072 KB Output is correct
8 Correct 33 ms 183132 KB Output is correct
9 Correct 32 ms 183124 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 32 ms 183120 KB Output is correct
12 Correct 32 ms 183044 KB Output is correct
13 Correct 30 ms 182980 KB Output is correct
14 Correct 31 ms 183132 KB Output is correct
15 Correct 31 ms 183128 KB Output is correct
16 Correct 34 ms 183132 KB Output is correct
17 Correct 32 ms 183120 KB Output is correct
18 Correct 31 ms 183132 KB Output is correct
19 Correct 31 ms 182952 KB Output is correct
20 Correct 32 ms 183132 KB Output is correct
21 Incorrect 30 ms 183068 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 151 ms 187020 KB Output is correct
2 Correct 134 ms 187212 KB Output is correct
3 Correct 139 ms 185168 KB Output is correct
4 Correct 149 ms 186960 KB Output is correct
5 Correct 136 ms 187216 KB Output is correct
6 Correct 136 ms 187088 KB Output is correct
7 Correct 47 ms 186192 KB Output is correct
8 Correct 49 ms 186504 KB Output is correct
9 Correct 138 ms 187044 KB Output is correct
10 Correct 131 ms 186960 KB Output is correct
11 Correct 140 ms 186952 KB Output is correct
12 Correct 137 ms 186960 KB Output is correct
13 Correct 127 ms 186964 KB Output is correct
14 Correct 135 ms 187476 KB Output is correct
15 Correct 131 ms 187388 KB Output is correct
16 Correct 152 ms 187472 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 191856 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 32 ms 183388 KB Output is correct
2 Correct 31 ms 183252 KB Output is correct
3 Correct 32 ms 183132 KB Output is correct
4 Correct 32 ms 183024 KB Output is correct
5 Correct 33 ms 183120 KB Output is correct
6 Correct 30 ms 183124 KB Output is correct
7 Correct 31 ms 183072 KB Output is correct
8 Correct 33 ms 183132 KB Output is correct
9 Correct 32 ms 183124 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 32 ms 183120 KB Output is correct
12 Correct 32 ms 183044 KB Output is correct
13 Correct 30 ms 182980 KB Output is correct
14 Correct 31 ms 183132 KB Output is correct
15 Correct 31 ms 183128 KB Output is correct
16 Correct 34 ms 183132 KB Output is correct
17 Correct 32 ms 183120 KB Output is correct
18 Correct 31 ms 183132 KB Output is correct
19 Correct 31 ms 182952 KB Output is correct
20 Correct 32 ms 183132 KB Output is correct
21 Correct 151 ms 187020 KB Output is correct
22 Correct 134 ms 187212 KB Output is correct
23 Correct 139 ms 185168 KB Output is correct
24 Correct 149 ms 186960 KB Output is correct
25 Correct 136 ms 187216 KB Output is correct
26 Correct 136 ms 187088 KB Output is correct
27 Correct 47 ms 186192 KB Output is correct
28 Correct 49 ms 186504 KB Output is correct
29 Correct 138 ms 187044 KB Output is correct
30 Correct 131 ms 186960 KB Output is correct
31 Correct 140 ms 186952 KB Output is correct
32 Correct 137 ms 186960 KB Output is correct
33 Correct 127 ms 186964 KB Output is correct
34 Correct 135 ms 187476 KB Output is correct
35 Correct 131 ms 187388 KB Output is correct
36 Correct 152 ms 187472 KB Output is correct
37 Correct 129 ms 186960 KB Output is correct
38 Correct 114 ms 186800 KB Output is correct
39 Correct 45 ms 186252 KB Output is correct
40 Correct 47 ms 186252 KB Output is correct
41 Correct 153 ms 186872 KB Output is correct
42 Correct 134 ms 186964 KB Output is correct
43 Correct 141 ms 187060 KB Output is correct
44 Correct 130 ms 186960 KB Output is correct
45 Correct 149 ms 186948 KB Output is correct
46 Correct 138 ms 186956 KB Output is correct
47 Correct 66 ms 186316 KB Output is correct
48 Correct 121 ms 186524 KB Output is correct
49 Correct 111 ms 186452 KB Output is correct
50 Correct 134 ms 186708 KB Output is correct
51 Correct 158 ms 186884 KB Output is correct
52 Correct 156 ms 187032 KB Output is correct
53 Correct 115 ms 186964 KB Output is correct
54 Correct 148 ms 187452 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 183388 KB Output is correct
2 Correct 31 ms 183252 KB Output is correct
3 Correct 32 ms 183132 KB Output is correct
4 Correct 32 ms 183024 KB Output is correct
5 Correct 33 ms 183120 KB Output is correct
6 Correct 30 ms 183124 KB Output is correct
7 Correct 31 ms 183072 KB Output is correct
8 Correct 33 ms 183132 KB Output is correct
9 Correct 32 ms 183124 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 32 ms 183120 KB Output is correct
12 Correct 32 ms 183044 KB Output is correct
13 Correct 30 ms 182980 KB Output is correct
14 Correct 31 ms 183132 KB Output is correct
15 Correct 31 ms 183128 KB Output is correct
16 Correct 34 ms 183132 KB Output is correct
17 Correct 32 ms 183120 KB Output is correct
18 Correct 31 ms 183132 KB Output is correct
19 Correct 31 ms 182952 KB Output is correct
20 Correct 32 ms 183132 KB Output is correct
21 Incorrect 30 ms 183068 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 183388 KB Output is correct
2 Correct 31 ms 183252 KB Output is correct
3 Correct 32 ms 183132 KB Output is correct
4 Correct 32 ms 183024 KB Output is correct
5 Correct 33 ms 183120 KB Output is correct
6 Correct 30 ms 183124 KB Output is correct
7 Correct 31 ms 183072 KB Output is correct
8 Correct 33 ms 183132 KB Output is correct
9 Correct 32 ms 183124 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 32 ms 183120 KB Output is correct
12 Correct 32 ms 183044 KB Output is correct
13 Correct 30 ms 182980 KB Output is correct
14 Correct 31 ms 183132 KB Output is correct
15 Correct 31 ms 183128 KB Output is correct
16 Correct 34 ms 183132 KB Output is correct
17 Correct 32 ms 183120 KB Output is correct
18 Correct 31 ms 183132 KB Output is correct
19 Correct 31 ms 182952 KB Output is correct
20 Correct 32 ms 183132 KB Output is correct
21 Incorrect 30 ms 183068 KB Output isn't correct
22 Halted 0 ms 0 KB -