제출 #237419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237419		jhnah917	가로등 (APIO19_street_lamps)	C++14	20 / 100	123 ms	5256 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;

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 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20