Submission #742663

#	Time	Username	Problem	Language	Result	Execution time	Memory
742663		He_Huanglu	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	129 ms	4308 KiB

street_lamps

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

const int N = 1e3 + 5;
int n, nq, a[N], bit[N][N], pre;
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, pre + 1, i + 1, i, 0, 0);
            pre = i;
        }
    }
    s.insert(0);
    s.insert(n);
//    s.insert(1);
//    s.erase(2);
//    up(4, 1, 2, 1, 1, 0);
//    up(4, 2, 3, 2, 3, 1);
//    cout << get(3, 1) << "\n";
//    return 0;
//    for(int i = 1; i <= n; i++) {
//        for(int j = i + 1; j <= n; j++) {
//            int tmp = 4;
//            if(*s.lower_bound(i) < j) tmp = 0;
////            cout << *s.lower_bound(i)
//            cout << i << " " << j << " : " << tmp << " " << get(j, i) << "\n";
//        }
//    }
//    return 0;
    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 = t;
            if(*s.lower_bound(v) < u) tmp = 0;
            cout << tmp - get(u, v) << "\n";
        }
        else {
            int i; cin >> i;
            a[i] = 1 - a[i];
            if(!a[i]) s.insert(i);
            else s.erase(i);
            int j = *(--(s.lower_bound(i)));
            int k = *s.upper_bound(i);
            up(k, j + 1, i + 1, i, t, a[i]);
//            cout << n << " " << j + 1 << " " << i + 1 << " " << i << " " << t << " " << a[i] << "\n";
        }
    }
}

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