oj.uz

Submission #237440

# Submission time Handle Problem Language Result Execution time Memory
237440 2020-06-06T15:13:56 Z jhnah917 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 209 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;
        if(op == 1){
            if(sub2_stat[a] == 1) sub2_ans[a] += i - sub2_now[a], sub2_now[a] = 0;
            else sub2_now[a] = i;
            sub2_stat[a] ^= 1;
        }else{
            cout << sub2_ans[a] + (i - sub2_now[a] + 1) * sub2_stat[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();
}

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 12288 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 123 ms 16896 KB Output is correct
5 Correct 127 ms 16896 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct
7 Correct 127 ms 17016 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 13048 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 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 108 ms 12812 KB Output is correct
6 Correct 144 ms 13068 KB Output is correct
7 Correct 176 ms 13196 KB Output is correct
8 Correct 209 ms 14860 KB Output is correct
9 Correct 98 ms 13048 KB Output is correct
10 Correct 107 ms 13048 KB Output is correct
11 Correct 108 ms 13176 KB Output is correct
12 Correct 187 ms 13456 KB Output is correct
13 Correct 208 ms 15116 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 12288 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 123 ms 16896 KB Output is correct
5 Correct 127 ms 16896 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct
7 Correct 127 ms 17016 KB Output is correct
8 Incorrect 83 ms 13048 KB Output isn't correct
9 Halted 0 ms 0 KB -