oj.uz

Submission #953051

# Submission time Handle Problem Language Result Execution time Memory
953051 2024-03-25T11:20:39 Z Vladth11 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 797 ms 205916 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 300001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

int n;

class AINT{
public:
    struct Node{
        int sum, st, dr;
    };
    vector <Node> aint;
    void update(int node, int st, int dr, int a, int b, int val){
        if(!aint.size()){
            aint.push_back({0, -1, -1});
        }
        if(a <= st && dr <= b){
            aint[node].sum += val;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid){
            if(aint[node].st == -1){
                aint[node].st = aint.size();
                aint.push_back({0, -1, -1});
            }
            update(aint[node].st, st, mid, a, b, val);
        }
        if(b > mid){
            if(aint[node].dr == -1){
                aint[node].dr = aint.size();
                aint.push_back({0, -1, -1});
            }
            update(aint[node].dr, mid + 1, dr, a, b, val);
        }
    }
    int query(int node, int st, int dr, int a){
        if(node == -1 || !aint.size()){
            return 0;
        }
        int aici = aint[node].sum;
        if(st == dr)
            return aici;
        int mid = (st + dr) / 2;
        if(a <= mid){
            return aici + query(aint[node].st, st, mid, a);
        }
        return aici + query(aint[node].dr, mid + 1, dr, a);
    }
}stt[NMAX * 4];

void update(int node, int st, int dr, int x1, int x2, int y1, int y2, int val){
    if(x2 < x1) return;
    if(y2 < y1) return;
    if(x1 <= st && dr <= x2){
        stt[node].update(0, 1, n, y1, y2, val);
        return;
    }
    int mid = (st + dr) / 2;
    if(x1 <= mid)
        update(node * 2, st, mid, x1, x2, y1, y2, val);
    if(x2 > mid)
        update(node * 2 + 1, mid + 1, dr, x1, x2, y1, y2, val);
}

int query(int node, int st, int dr, int x, int y){
    int aici = stt[node].query(0, 1, n, y);
    if(st == dr){
        return aici;
    }
    int mid = (st + dr) / 2;
    if(x <= mid)
        return aici + query(node * 2, st, mid, x, y);
    return aici + query(node * 2 + 1, mid + 1, dr, x, y);
}

int a[NMAX];
string s[NMAX];
int qa[NMAX];
int qb[NMAX];

int aib[NMAX * 4];

void upd(int node, int val){
    for(; node <= n; node += node&(-node))
        aib[node] += val;
}

int qry(int node){
    int val = 0;
    for(; node; node -= node&(-node))
        val += aib[node];
    return val;
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, q;
    cin >> n >> q;
    for(i = 1; i <= n; i++){
        char c;
        cin >> c;
        a[i] = c - '0';
        upd(i, a[i]);
    }
    for(i = 1; i <= q; i++){
        cin >> s[i];
        cin >> qa[i];
        if(s[i][0] == 'q'){
            cin >> qb[i];
            qb[i]--;
            cout << query(1, 1, n, qa[i], qb[i]) + i * ((qry(qb[i]) - qry(qa[i] - 1)) == (qb[i] - qa[i] + 1)) << "\n";
        }else{
            if(a[qa[i]] == 1){
                int r = 0, pas = (1 << nrbits);
                while(pas){
                    if(r + pas <= qa[i] && qry(qa[i]) - qry(r + pas - 1) != (qa[i] - (r + pas) + 1))
                        r += pas;
                    pas /= 2;
                }
                r++;
                int st = r;
                r = qa[i], pas = (1 << nrbits);
                while(pas){
                    if(r + pas <= n && qry(r + pas) - qry(qa[i] - 1) == ((r + pas) - qa[i] + 1))
                        r += pas;
                    pas /= 2;
                }
                int dr = r;
                update(1, 1, n, st, qa[i], qa[i], dr, i);
            }else{
                int r = 0, pas = (1 << nrbits);
                while(pas){
                    if(r + pas < qa[i] && qry(qa[i]) - qry(r + pas - 1) != (qa[i] - (r + pas)))
                        r += pas;
                    pas /= 2;
                }
                r++;
                int st = r;
                r = qa[i], pas = (1 << nrbits);
                while(pas){
                    if(r + pas <= n && qry(r + pas) - qry(qa[i] - 1) == ((r + pas) - qa[i]))
                        r += pas;
                    pas /= 2;
                }
                int dr = r;
                update(1, 1, n, st, qa[i], qa[i], dr, -i);
            }
            upd(qa[i], -a[qa[i]]);
            a[qa[i]] ^= 1;
            upd(qa[i], a[qa[i]]);
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 41820 KB Output is correct
2 Correct 9 ms 41972 KB Output is correct
3 Correct 10 ms 41820 KB Output is correct
4 Correct 10 ms 41932 KB Output is correct
5 Correct 9 ms 41820 KB Output is correct
6 Correct 9 ms 41820 KB Output is correct
7 Correct 9 ms 41816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 44996 KB Output is correct
2 Correct 168 ms 46512 KB Output is correct
3 Correct 239 ms 50256 KB Output is correct
4 Correct 468 ms 108796 KB Output is correct
5 Correct 549 ms 148528 KB Output is correct
6 Correct 504 ms 116416 KB Output is correct
7 Correct 168 ms 50632 KB Output is correct
8 Correct 183 ms 51920 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42072 KB Output is correct
2 Correct 10 ms 42076 KB Output is correct
3 Correct 10 ms 42076 KB Output is correct
4 Correct 10 ms 41816 KB Output is correct
5 Correct 797 ms 205916 KB Output is correct
6 Correct 662 ms 181392 KB Output is correct
7 Correct 530 ms 147596 KB Output is correct
8 Correct 172 ms 51984 KB Output is correct
9 Correct 76 ms 45416 KB Output is correct
10 Correct 81 ms 45908 KB Output is correct
11 Correct 84 ms 46160 KB Output is correct
12 Correct 170 ms 50488 KB Output is correct
13 Correct 203 ms 51912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 41988 KB Output is correct
2 Correct 9 ms 41820 KB Output is correct
3 Correct 10 ms 41908 KB Output is correct
4 Correct 10 ms 42164 KB Output is correct
5 Correct 172 ms 46416 KB Output is correct
6 Correct 349 ms 89172 KB Output is correct
7 Correct 471 ms 116056 KB Output is correct
8 Correct 717 ms 141060 KB Output is correct
9 Correct 175 ms 45700 KB Output is correct
10 Correct 136 ms 45000 KB Output is correct
11 Correct 175 ms 45836 KB Output is correct
12 Correct 136 ms 44880 KB Output is correct
13 Correct 169 ms 45648 KB Output is correct
14 Correct 136 ms 44844 KB Output is correct
15 Correct 179 ms 50516 KB Output is correct
16 Correct 174 ms 52160 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 41820 KB Output is correct
2 Correct 9 ms 41972 KB Output is correct
3 Correct 10 ms 41820 KB Output is correct
4 Correct 10 ms 41932 KB Output is correct
5 Correct 9 ms 41820 KB Output is correct
6 Correct 9 ms 41820 KB Output is correct
7 Correct 9 ms 41816 KB Output is correct
8 Correct 132 ms 44996 KB Output is correct
9 Correct 168 ms 46512 KB Output is correct
10 Correct 239 ms 50256 KB Output is correct
11 Correct 468 ms 108796 KB Output is correct
12 Correct 549 ms 148528 KB Output is correct
13 Correct 504 ms 116416 KB Output is correct
14 Correct 168 ms 50632 KB Output is correct
15 Correct 183 ms 51920 KB Output is correct
16 Correct 10 ms 42072 KB Output is correct
17 Correct 10 ms 42076 KB Output is correct
18 Correct 10 ms 42076 KB Output is correct
19 Correct 10 ms 41816 KB Output is correct
20 Correct 797 ms 205916 KB Output is correct
21 Correct 662 ms 181392 KB Output is correct
22 Correct 530 ms 147596 KB Output is correct
23 Correct 172 ms 51984 KB Output is correct
24 Correct 76 ms 45416 KB Output is correct
25 Correct 81 ms 45908 KB Output is correct
26 Correct 84 ms 46160 KB Output is correct
27 Correct 170 ms 50488 KB Output is correct
28 Correct 203 ms 51912 KB Output is correct
29 Correct 10 ms 41988 KB Output is correct
30 Correct 9 ms 41820 KB Output is correct
31 Correct 10 ms 41908 KB Output is correct
32 Correct 10 ms 42164 KB Output is correct
33 Correct 172 ms 46416 KB Output is correct
34 Correct 349 ms 89172 KB Output is correct
35 Correct 471 ms 116056 KB Output is correct
36 Correct 717 ms 141060 KB Output is correct
37 Correct 175 ms 45700 KB Output is correct
38 Correct 136 ms 45000 KB Output is correct
39 Correct 175 ms 45836 KB Output is correct
40 Correct 136 ms 44880 KB Output is correct
41 Correct 169 ms 45648 KB Output is correct
42 Correct 136 ms 44844 KB Output is correct
43 Correct 179 ms 50516 KB Output is correct
44 Correct 174 ms 52160 KB Output is correct
45 Correct 63 ms 44252 KB Output is correct
46 Correct 90 ms 44536 KB Output is correct
47 Correct 249 ms 77888 KB Output is correct
48 Correct 480 ms 108372 KB Output is correct
49 Correct 86 ms 45904 KB Output is correct
50 Correct 95 ms 45916 KB Output is correct
51 Correct 94 ms 46164 KB Output is correct
52 Correct 89 ms 46420 KB Output is correct
53 Correct 105 ms 46484 KB Output is correct
54 Correct 89 ms 46524 KB Output is correct