oj.uz

Submission #976436

# Submission time Handle Problem Language Result Execution time Memory
976436 2024-05-06T14:53:10 Z underwaterkillerwhale Food Court (JOI21_foodcourt) C++17
24 / 100
 167 ms 189124 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) {
            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 100 ms 183120 KB Output is correct
2 Correct 33 ms 183128 KB Output is correct
3 Correct 30 ms 183132 KB Output is correct
4 Correct 31 ms 183120 KB Output is correct
5 Correct 29 ms 183016 KB Output is correct
6 Correct 29 ms 183120 KB Output is correct
7 Correct 37 ms 183132 KB Output is correct
8 Correct 34 ms 183376 KB Output is correct
9 Correct 32 ms 183108 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 31 ms 183120 KB Output is correct
12 Correct 33 ms 182912 KB Output is correct
13 Correct 31 ms 183088 KB Output is correct
14 Correct 30 ms 182960 KB Output is correct
15 Correct 31 ms 183132 KB Output is correct
16 Correct 31 ms 182956 KB Output is correct
17 Correct 31 ms 183132 KB Output is correct
18 Correct 32 ms 182964 KB Output is correct
19 Correct 32 ms 182936 KB Output is correct
20 Correct 31 ms 183132 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 183120 KB Output is correct
2 Correct 33 ms 183128 KB Output is correct
3 Correct 30 ms 183132 KB Output is correct
4 Correct 31 ms 183120 KB Output is correct
5 Correct 29 ms 183016 KB Output is correct
6 Correct 29 ms 183120 KB Output is correct
7 Correct 37 ms 183132 KB Output is correct
8 Correct 34 ms 183376 KB Output is correct
9 Correct 32 ms 183108 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 31 ms 183120 KB Output is correct
12 Correct 33 ms 182912 KB Output is correct
13 Correct 31 ms 183088 KB Output is correct
14 Correct 30 ms 182960 KB Output is correct
15 Correct 31 ms 183132 KB Output is correct
16 Correct 31 ms 182956 KB Output is correct
17 Correct 31 ms 183132 KB Output is correct
18 Correct 32 ms 182964 KB Output is correct
19 Correct 32 ms 182936 KB Output is correct
20 Correct 31 ms 183132 KB Output is correct
21 Incorrect 30 ms 182908 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 131 ms 186984 KB Output is correct
2 Correct 134 ms 187216 KB Output is correct
3 Correct 132 ms 185172 KB Output is correct
4 Correct 130 ms 187000 KB Output is correct
5 Correct 137 ms 186968 KB Output is correct
6 Correct 150 ms 186980 KB Output is correct
7 Correct 47 ms 185936 KB Output is correct
8 Correct 48 ms 186320 KB Output is correct
9 Correct 123 ms 186756 KB Output is correct
10 Correct 135 ms 186960 KB Output is correct
11 Correct 127 ms 186960 KB Output is correct
12 Correct 139 ms 186708 KB Output is correct
13 Correct 123 ms 186960 KB Output is correct
14 Correct 147 ms 187476 KB Output is correct
15 Correct 126 ms 187108 KB Output is correct
16 Correct 148 ms 187500 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 189124 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 100 ms 183120 KB Output is correct
2 Correct 33 ms 183128 KB Output is correct
3 Correct 30 ms 183132 KB Output is correct
4 Correct 31 ms 183120 KB Output is correct
5 Correct 29 ms 183016 KB Output is correct
6 Correct 29 ms 183120 KB Output is correct
7 Correct 37 ms 183132 KB Output is correct
8 Correct 34 ms 183376 KB Output is correct
9 Correct 32 ms 183108 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 31 ms 183120 KB Output is correct
12 Correct 33 ms 182912 KB Output is correct
13 Correct 31 ms 183088 KB Output is correct
14 Correct 30 ms 182960 KB Output is correct
15 Correct 31 ms 183132 KB Output is correct
16 Correct 31 ms 182956 KB Output is correct
17 Correct 31 ms 183132 KB Output is correct
18 Correct 32 ms 182964 KB Output is correct
19 Correct 32 ms 182936 KB Output is correct
20 Correct 31 ms 183132 KB Output is correct
21 Correct 131 ms 186984 KB Output is correct
22 Correct 134 ms 187216 KB Output is correct
23 Correct 132 ms 185172 KB Output is correct
24 Correct 130 ms 187000 KB Output is correct
25 Correct 137 ms 186968 KB Output is correct
26 Correct 150 ms 186980 KB Output is correct
27 Correct 47 ms 185936 KB Output is correct
28 Correct 48 ms 186320 KB Output is correct
29 Correct 123 ms 186756 KB Output is correct
30 Correct 135 ms 186960 KB Output is correct
31 Correct 127 ms 186960 KB Output is correct
32 Correct 139 ms 186708 KB Output is correct
33 Correct 123 ms 186960 KB Output is correct
34 Correct 147 ms 187476 KB Output is correct
35 Correct 126 ms 187108 KB Output is correct
36 Correct 148 ms 187500 KB Output is correct
37 Correct 123 ms 186684 KB Output is correct
38 Correct 106 ms 186704 KB Output is correct
39 Correct 48 ms 185928 KB Output is correct
40 Correct 47 ms 186244 KB Output is correct
41 Correct 129 ms 186812 KB Output is correct
42 Correct 134 ms 186960 KB Output is correct
43 Correct 141 ms 186960 KB Output is correct
44 Correct 167 ms 186768 KB Output is correct
45 Correct 143 ms 186796 KB Output is correct
46 Correct 154 ms 186900 KB Output is correct
47 Correct 66 ms 186252 KB Output is correct
48 Correct 115 ms 186560 KB Output is correct
49 Correct 121 ms 186408 KB Output is correct
50 Correct 137 ms 186708 KB Output is correct
51 Correct 148 ms 186704 KB Output is correct
52 Correct 151 ms 186792 KB Output is correct
53 Correct 118 ms 187100 KB Output is correct
54 Correct 157 ms 187476 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 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 100 ms 183120 KB Output is correct
2 Correct 33 ms 183128 KB Output is correct
3 Correct 30 ms 183132 KB Output is correct
4 Correct 31 ms 183120 KB Output is correct
5 Correct 29 ms 183016 KB Output is correct
6 Correct 29 ms 183120 KB Output is correct
7 Correct 37 ms 183132 KB Output is correct
8 Correct 34 ms 183376 KB Output is correct
9 Correct 32 ms 183108 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 31 ms 183120 KB Output is correct
12 Correct 33 ms 182912 KB Output is correct
13 Correct 31 ms 183088 KB Output is correct
14 Correct 30 ms 182960 KB Output is correct
15 Correct 31 ms 183132 KB Output is correct
16 Correct 31 ms 182956 KB Output is correct
17 Correct 31 ms 183132 KB Output is correct
18 Correct 32 ms 182964 KB Output is correct
19 Correct 32 ms 182936 KB Output is correct
20 Correct 31 ms 183132 KB Output is correct
21 Incorrect 30 ms 182908 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 183120 KB Output is correct
2 Correct 33 ms 183128 KB Output is correct
3 Correct 30 ms 183132 KB Output is correct
4 Correct 31 ms 183120 KB Output is correct
5 Correct 29 ms 183016 KB Output is correct
6 Correct 29 ms 183120 KB Output is correct
7 Correct 37 ms 183132 KB Output is correct
8 Correct 34 ms 183376 KB Output is correct
9 Correct 32 ms 183108 KB Output is correct
10 Correct 31 ms 183124 KB Output is correct
11 Correct 31 ms 183120 KB Output is correct
12 Correct 33 ms 182912 KB Output is correct
13 Correct 31 ms 183088 KB Output is correct
14 Correct 30 ms 182960 KB Output is correct
15 Correct 31 ms 183132 KB Output is correct
16 Correct 31 ms 182956 KB Output is correct
17 Correct 31 ms 183132 KB Output is correct
18 Correct 32 ms 182964 KB Output is correct
19 Correct 32 ms 182936 KB Output is correct
20 Correct 31 ms 183132 KB Output is correct
21 Incorrect 30 ms 182908 KB Output isn't correct
22 Halted 0 ms 0 KB -