oj.uz

Submission #742663

# Submission time Handle Problem Language Result Execution time Memory
742663 2023-05-16T16:37:07 Z He_Huanglu Street Lamps (APIO19_street_lamps) C++17
20 / 100
 129 ms 4308 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1660 KB Output is correct
2 Correct 129 ms 2460 KB Output is correct
3 Runtime error 2 ms 468 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 3668 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3668 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Runtime error 1 ms 524 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 106 ms 1660 KB Output is correct
9 Correct 129 ms 2460 KB Output is correct
10 Runtime error 2 ms 468 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -