oj.uz

Submission #755237

# Submission time Handle Problem Language Result Execution time Memory
755237 2023-06-09T16:02:07 Z Ahmed57 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3106 ms 111240 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
vector<int> node[N], bit[N];
int n;
void fakeup (int x, int y) {
    for(x; x <= n; x += x & -x) node[x].push_back(y);
}
void up(int x, int yy, int val) {
    if (yy > n) return;
    for(x; x <= n; x += x & -x) {
        for(int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y <= node[x].size(); y += y & -y) {
            bit[x][y] += val;
        }
    }
}
int get(int x, int yy) {
    int ret = 0;
    for(x; x; x -= x & -x) {
        for(int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y; y -= y & -y) {
            ret += bit[x][y];
        }
    }
    return ret;
}
void compress() {
    for(int i = 1; i <= n; i++) {
        sort(node[i].begin(), node[i].end());
        node[i].resize(unique(node[i].begin(), node[i].end()) - node[i].begin());
        bit[i].resize(node[i].size() + 1);
    }
}
void fakeinc(int x, int y, int u, int v) {
    fakeup(x, y);
    fakeup(x, v + 1);
    fakeup(u + 1, y);
    fakeup(u + 1, v + 1);
}
void inc(int x, int y, int u, int v, int val) {
    up(x, y, val);
    up(x, v + 1, -val);
    up(u + 1, y, -val);
    up(u + 1, v + 1, val);
}
int q;
signed main() {
    cin>>n>>q;
    string s;cin>>s;s = " "+s;
    int lol[n+1] = {0};
    set<int> ind;
    ind.insert(0);ind.insert(n+1);
    for(int i = 1;i<=n;i++){
        lol[i] = s[i]-'0';
        if(!lol[i])ind.insert(i);
    }
    int que[q+1][3];
    int xd[q+1][2];
    int ans[q+1] = {0};
    for(int i = 1;i<=q;i++){
        string ty;cin>>ty;
        if(ty[0]=='t'){
            int x;cin>>x;
            lol[x]^=1;
            if(lol[x])ind.erase(ind.find(x));
            else ind.insert(x);
            auto it = ind.upper_bound(x);
            int r = *it-1;
            it--;
            if(*it==x)it--;
            int l = *it+1;
            fakeinc(l,x,x,r);
            que[i][0] = 0;
            que[i][1] = l;
            que[i][2] = r;
            xd[i][0] = x;
            xd[i][1] = (lol[x]?-i:i);
        }else{
            int a,b;cin>>a>>b;
            b--;
            que[i][0] = 1;
            que[i][1] = a;
            que[i][2] = b;
            if(*ind.lower_bound(a)>b){
                ans[i]+=i;
            }
        }
    }
    compress();
    for(int i = 1;i<=q;i++){
        if(que[i][0]==0){
            inc(que[i][1],xd[i][0],xd[i][0],que[i][2],xd[i][1]);
        }else{
            cout<<ans[i]+get(que[i][1],que[i][2])<<endl;
        }
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'void fakeup(int, int)':
street_lamps.cpp:7:9: warning: statement has no effect [-Wunused-value]
    7 |     for(x; x <= n; x += x & -x) node[x].push_back(y);
      |         ^
street_lamps.cpp: In function 'void up(int, int, int)':
street_lamps.cpp:11:9: warning: statement has no effect [-Wunused-value]
   11 |     for(x; x <= n; x += x & -x) {
      |         ^
street_lamps.cpp:12:90: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for(int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y <= node[x].size(); y += y & -y) {
      |                                                                                        ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int get(int, int)':
street_lamps.cpp:19:9: warning: statement has no effect [-Wunused-value]
   19 |     for(x; x; x -= x & -x) {
      |         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 10 ms 14392 KB Output is correct
3 Correct 11 ms 14392 KB Output is correct
4 Correct 9 ms 14352 KB Output is correct
5 Correct 10 ms 14388 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 36124 KB Output is correct
2 Correct 746 ms 38304 KB Output is correct
3 Correct 970 ms 45124 KB Output is correct
4 Correct 1968 ms 82764 KB Output is correct
5 Correct 1767 ms 68636 KB Output is correct
6 Correct 2090 ms 91144 KB Output is correct
7 Correct 1052 ms 52924 KB Output is correct
8 Correct 750 ms 40244 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14548 KB Output is correct
2 Correct 13 ms 14548 KB Output is correct
3 Correct 11 ms 14500 KB Output is correct
4 Correct 11 ms 14376 KB Output is correct
5 Correct 3106 ms 105764 KB Output is correct
6 Correct 2557 ms 90828 KB Output is correct
7 Correct 1809 ms 68060 KB Output is correct
8 Correct 664 ms 40416 KB Output is correct
9 Correct 449 ms 23740 KB Output is correct
10 Correct 524 ms 24652 KB Output is correct
11 Correct 513 ms 24780 KB Output is correct
12 Correct 921 ms 53020 KB Output is correct
13 Correct 739 ms 40148 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 11 ms 14420 KB Output is correct
3 Correct 12 ms 14528 KB Output is correct
4 Correct 10 ms 14548 KB Output is correct
5 Correct 969 ms 46920 KB Output is correct
6 Correct 1493 ms 70236 KB Output is correct
7 Correct 1907 ms 90776 KB Output is correct
8 Correct 2595 ms 111240 KB Output is correct
9 Correct 608 ms 48128 KB Output is correct
10 Correct 448 ms 45412 KB Output is correct
11 Correct 648 ms 48548 KB Output is correct
12 Correct 483 ms 45684 KB Output is correct
13 Correct 614 ms 48660 KB Output is correct
14 Correct 461 ms 45800 KB Output is correct
15 Correct 944 ms 53000 KB Output is correct
16 Correct 688 ms 40208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 10 ms 14392 KB Output is correct
3 Correct 11 ms 14392 KB Output is correct
4 Correct 9 ms 14352 KB Output is correct
5 Correct 10 ms 14388 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct
8 Correct 666 ms 36124 KB Output is correct
9 Correct 746 ms 38304 KB Output is correct
10 Correct 970 ms 45124 KB Output is correct
11 Correct 1968 ms 82764 KB Output is correct
12 Correct 1767 ms 68636 KB Output is correct
13 Correct 2090 ms 91144 KB Output is correct
14 Correct 1052 ms 52924 KB Output is correct
15 Correct 750 ms 40244 KB Output is correct
16 Correct 12 ms 14548 KB Output is correct
17 Correct 13 ms 14548 KB Output is correct
18 Correct 11 ms 14500 KB Output is correct
19 Correct 11 ms 14376 KB Output is correct
20 Correct 3106 ms 105764 KB Output is correct
21 Correct 2557 ms 90828 KB Output is correct
22 Correct 1809 ms 68060 KB Output is correct
23 Correct 664 ms 40416 KB Output is correct
24 Correct 449 ms 23740 KB Output is correct
25 Correct 524 ms 24652 KB Output is correct
26 Correct 513 ms 24780 KB Output is correct
27 Correct 921 ms 53020 KB Output is correct
28 Correct 739 ms 40148 KB Output is correct
29 Correct 9 ms 14420 KB Output is correct
30 Correct 11 ms 14420 KB Output is correct
31 Correct 12 ms 14528 KB Output is correct
32 Correct 10 ms 14548 KB Output is correct
33 Correct 969 ms 46920 KB Output is correct
34 Correct 1493 ms 70236 KB Output is correct
35 Correct 1907 ms 90776 KB Output is correct
36 Correct 2595 ms 111240 KB Output is correct
37 Correct 608 ms 48128 KB Output is correct
38 Correct 448 ms 45412 KB Output is correct
39 Correct 648 ms 48548 KB Output is correct
40 Correct 483 ms 45684 KB Output is correct
41 Correct 614 ms 48660 KB Output is correct
42 Correct 461 ms 45800 KB Output is correct
43 Correct 944 ms 53000 KB Output is correct
44 Correct 688 ms 40208 KB Output is correct
45 Correct 279 ms 26004 KB Output is correct
46 Correct 346 ms 28140 KB Output is correct
47 Correct 1024 ms 49400 KB Output is correct
48 Correct 1836 ms 82964 KB Output is correct
49 Correct 572 ms 25552 KB Output is correct
50 Correct 578 ms 25496 KB Output is correct
51 Correct 566 ms 25720 KB Output is correct
52 Correct 595 ms 26068 KB Output is correct
53 Correct 548 ms 26160 KB Output is correct
54 Correct 599 ms 26032 KB Output is correct