Submission #237833

#	Time	Username	Problem	Language	Result	Execution time	Memory
237833		jhnah917	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	209 ms	23436 KiB

street_lamps

#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;

int sub3_chk[303030];
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] = 0, 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]) sub2_ans[a] += i - sub2_now[a];
            sub2_now[a] = i; sub2_stat[a] ^= 1;
        }else{
            int ans = sub2_ans[a] + (i - sub2_now[a]) * sub2_stat[a];
            cout << ans << "\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, is_3 = true;
    cin >> st;
    for(int i=1; i<=q; i++){
        string _op; int op, a, b;
        cin >> _op >> a;
        if(_op == "toggle"){
            op = 1;
            if(sub3_chk[a]) is_3 = false;
            else sub3_chk[a] = true;
	}
        else{
            op = 2; cin >> b;
            if(b - a != 1) is_2 = false;
        }
        qry[i] = {op, a, b};
    }
    if(is_2){
        sub2(); return 0;
    }
    if(is_3){
        sub3(); return 0;
    }
    exit(-1);
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20