oj.uz

Submission #237419

# Submission time Handle Problem Language Result Execution time Memory
237419 2020-06-06T14:27:56 Z jhnah917 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 123 ms 5256 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;

int n, q;

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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 116 ms 5240 KB Output is correct
5 Correct 120 ms 5240 KB Output is correct
6 Correct 123 ms 5120 KB Output is correct
7 Correct 122 ms 5256 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 116 ms 5240 KB Output is correct
5 Correct 120 ms 5240 KB Output is correct
6 Correct 123 ms 5120 KB Output is correct
7 Correct 122 ms 5256 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -