oj.uz

Submission #237436

# Submission time Handle Problem Language Result Execution time Memory
237436 2020-06-06T15:09:51 Z jhnah917 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 213 ms 17016 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

struct Query{
    int op, a, b;
    Query(int op, int a, int b) : op(op), a(a), b(b) {}
    Query() : Query(0, 0, 0) {}
};

int n, q;
string st;
Query qry[303030];

void sub1_floyd(int a[111][111][111], int b){
    for(int i=1; i<=n+1; i++) for(int j=1; j<=n+1; j++) a[i][j][b+1] = a[i][j][b];
    for(int k=1; k<=n+1; k++) for(int i=1; i<=n+1; i++) for(int j=1; j<=n+1; j++){
        if(a[i][k][b] && a[k][j][b]) a[i][j][b] = 1;
    }
}

int sub1_ans[111][111][111] = {0};
void sub1(){
    string s; cin >> s;
    for(int i=1; i<=n; i++){
        if(s[i-1] == '1') sub1_ans[i][i + 1][0] = 1;
    }
    sub1_floyd(sub1_ans, 0);
    for(int i=1; i<=q; i++){
        string op; int a, b; cin >> op;
        if(op == "toggle"){
            cin >> a;
            sub1_ans[a][a + 1][i] ^= 1;
            sub1_floyd(sub1_ans, i);
        }else{
            cin >> a >> b;
            int cnt = 0;
            for(int j=0; j<i; j++) cnt += sub1_ans[a][b][j];
            cout << cnt << "\n";
            sub1_floyd(sub1_ans, i);
        }
    }
}

int sz = 1 << 19;
struct Sub3_Seg{
    int tree[1 << 20][2];
    Sub3_Seg(){
        for(int i=0; i<(1<<20); i++){
            tree[i][0] = -1; tree[i][1] = 0;
        }
    }
    void update(int x, int v){
        x |= sz; tree[x][0] = v; tree[x][1] = 1;
        while(x >>= 1){
            tree[x][0] = max(tree[x << 1][0], tree[x << 1 | 1][0]);
            tree[x][1] = tree[x << 1][1] + tree[x << 1 | 1][1];
        }
    }
    int query(int l, int r){
        int range = r - l + 1;
        l |= sz; r |= sz; int ret = 0, sum = 0;
        while(l <= r){
            if(l & 1) sum += tree[l][1], ret = max(ret, tree[l][0]), l++;
            if(~r & 1) sum += tree[r][1], ret = max(ret, tree[r][0]), r--;
            l >>= 1; r >>= 1;
        }
        if(sum != range) return -1;
        return ret;
    }
} sub3seg;

void sub3(){
    string s = st;
    for(int i=1; i<=n; i++){
        if(s[i-1] == '1') sub3seg.update(i, 0);
    }
    for(int i=1; i<=q; i++){
        int op = qry[i].op, a = qry[i].a, b = qry[i].b;
        if(op == 1){
            cin >> a;
            sub3seg.update(a, i);
        }else{
            cin >> a >> b;
            int t = sub3seg.query(a, b-1);
            if(t == -1) cout << 0 << "\n";
            else cout << i - t << "\n";
        }
    }
}

int sub2_ans[303030], sub2_now[303030], sub2_stat[303030];
void sub2(){
    string s = st;
    for(int i=1; i<=n; i++){
        if(s[i-1] == '1') sub2_now[i]++, sub2_stat[i] = 1;
    }
    for(int i=1; i<=q; i++){
        int op = qry[i].op, a = qry[i].a, b = qry[i].b;
        if(op == 1){
            if(sub2_stat[a] == 1) sub2_ans[a] += sub2_now[a], sub2_now[a] = 0;
            else sub2_now[a] = 1;
            sub2_stat[a] ^= 1;
        }else{
            cout << sub2_ans[a] + sub2_now[a] <<"\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    if(n <= 100 && q <= 100){
        sub1(); return 0;
    }

    bool is_2 = true;
    cin >> st;
    for(int i=1; i<=q; i++){
        string _op; int op, a, b;
        cin >> _op >> a;
        if(_op == "toggle") op = 1;
        else{
            op = 2; cin >> b;
            if(b - a != 1) is_2 = false;
        }
        qry[i] = {op, a, b};
    }
    if(is_2){
        sub2(); return 0;
    }
    sub3();
}

Compilation message

street_lamps.cpp: In function 'void sub2()':
street_lamps.cpp:102:43: warning: unused variable 'b' [-Wunused-variable]
         int op = qry[i].op, a = qry[i].a, b = qry[i].b;
                                           ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Correct 128 ms 16896 KB Output is correct
5 Correct 128 ms 16896 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct
7 Correct 135 ms 17016 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12180 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 113 ms 13196 KB Output is correct
6 Correct 139 ms 13516 KB Output is correct
7 Correct 176 ms 13708 KB Output is correct
8 Correct 213 ms 15244 KB Output is correct
9 Correct 95 ms 13304 KB Output is correct
10 Correct 109 ms 13384 KB Output is correct
11 Correct 110 ms 13560 KB Output is correct
12 Correct 190 ms 13836 KB Output is correct
13 Correct 208 ms 15248 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Incorrect 11 ms 12160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Correct 128 ms 16896 KB Output is correct
5 Correct 128 ms 16896 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct
7 Correct 135 ms 17016 KB Output is correct
8 Incorrect 84 ms 12920 KB Output isn't correct
9 Halted 0 ms 0 KB -