Submission #742615

#	Time	Username	Problem	Language	Result	Execution time	Memory
742615		He_Huanglu	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	115 ms	4924 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
int n, nq, a[N], bit[N][N];
set <int> s;

void upd(int x, int _y, int last, int i) {
    while (x) {
        int y = _y;
        while (y <= n) {
            bit[x][y] += (i ? last : -last);
//            cout << x << " " << y << " " << bit[x][y] << "^^\n";
            y += (y & -y);
        }
        x -= (x & -x);
    }
}

void up(int x, int y, int u, int v, int last, int i) {
    upd(x, y, last, i);
    upd(x, v + 1, last, 1 - i);
    upd(u - 1, y, last, 1 - i);
    upd(u - 1, v + 1, last, i);
}

int get(int x, int _y) {
    int ret = 0;
    while (x <= n) {
        int y = _y;
        while (y) {
            ret += bit[x][y];
//            cout << x << " " << y << " " << bit[x][y] << "**\n";
            y -= (y & -y);
        }
        x += (x & -x);
    }
    return ret;
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> nq; n++;
    for(int i = 1; i < n; i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
        if(!a[i]) {
            s.insert(i);
            up(n, 1, i, i, 0, 0);
        }
    }
    s.insert(0);
    s.insert(1e9);
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            int tmp = 1;
            if(*s.lower_bound(i) <= j) tmp = 0; //, cout << *s.lower_bound(i) << "%%\n";
//            cout << i << " " << j << " " << tmp << " : " << tmp - get(j, i) << "\n";
        }
    }
    for(int t = 1; t <= nq; t++) {
        string str; cin >> str;
        if(str == "query") {
            int u, v; cin >> u >> v;
            if(u < v) swap(u, v);
            int tmp = get(u, v);
            if(*s.lower_bound(v) <= u) cout << -tmp << "\n";
            else cout << t - tmp << "\n";
        }
        else {
            int i; cin >> i;
            a[i] = 1 - a[i];
            int j = *(--(s.lower_bound(i)));
            up(n, j + 1, i, i, t, a[i]);
            if(!a[i]) s.insert(i);
            else s.erase(i);
        }
    }
}

Compilation message (stderr)

street_lamps.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main () {
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:60:17: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
   60 |             int tmp = 1;
      |                 ^~~
street_lamps.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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