oj.uz

Submission #739159

# Submission time Handle Problem Language Result Execution time Memory
739159 2023-05-10T05:08:25 Z nguyentunglam Street Lamps (APIO19_street_lamps) C++17
40 / 100
 4403 ms 524288 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 3e5 + 10;
int a[N], ans[N];
int n, q;
tuple<int, int, int> query[N];
pair<int, int> tt[N];
vector<int> node[N], bit[N];
void fakeup (int x, int yy) {
    for(x; x <= n; x += x & -x) {
        for(int y = yy; y <= n; y += y & -y) {
            node[x].push_back(y);
        }
    }
}
void up(int x, int yy, int val) {
    if (yy > n) return;
    for(x; x <= n; x += x & -x) {
        for(int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y <= node[x].size(); y += y & -y) {
            bit[x][y] += val;
        }
    }
}
int get(int x, int yy) {
    int ret = 0;
    for(x; x; x -= x & -x) {
        for(int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y; y -= y & -y) {
            ret += bit[x][y];
        }
    }
    return ret;
}
void compress() {
    for(int i = 1; i <= n; i++) {
        sort(node[i].begin(), node[i].end());
        node[i].resize(unique(node[i].begin(), node[i].end()) - node[i].begin());
        bit[i].resize(node[i].size() + 1);
    }
}
void fakeinc(int x, int y, int u, int v) {
    fakeup(x, y);
    fakeup(x, v + 1);
    fakeup(u + 1, y);
    fakeup(u + 1, v + 1);
}
void inc(int x, int y, int u, int v, int val) {
    up(x, y, val);
    up(x, v + 1, -val);
    up(u + 1, y, -val);
    up(u + 1, v + 1, val);
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> q;
    string str; cin >> str; str = " " + str;
    set<int> s = {0, n + 1};
    for(int i = 1; i <= n; i++) {
        a[i] = str[i] - '0';
        if (!a[i]) s.insert(i);
    }
    for(int timer = 1; timer <= q; timer++) {
        string ask; cin >> ask;
        if (ask[0] == 't') {
            int i; cin >> i;
            a[i] ^= 1;
            if (a[i]) s.erase(s.find(i));
            else s.insert(i);
            auto it = s.upper_bound(i);
            int r = *it - 1;
            it--;
            if (*it == i) it--;
            int l = *it + 1;
            fakeinc(l, i, i, r);
//            cout << l << " " << i << " " << r << endl;
            query[timer] = {0, l, r};
            tt[timer].fi = i;
            tt[timer].se = a[i] ? -timer : timer;
        }
        else {
            int l, r; cin >> l >> r; r--;
            query[timer] = {1, l, r};
            if (*s.lower_bound(l) > r) ans[timer] += timer;
        }
    }
    compress();
    for(int timer = 1; timer <= q; timer++) {
        int type, l, r; tie(type, l, r) = query[timer];
        if (type == 0) {
            int i, val; tie(i, val) = tt[timer];
            inc(l, i, i, r, val);
        }
        else cout << get(l, r) + ans[timer] << endl;
    }
}

Compilation message

street_lamps.cpp: In function 'void fakeup(int, int)':
street_lamps.cpp:14:9: warning: statement has no effect [-Wunused-value]
   14 |     for(x; x <= n; x += x & -x) {
      |         ^
street_lamps.cpp: In function 'void up(int, int, int)':
street_lamps.cpp:22:9: warning: statement has no effect [-Wunused-value]
   22 |     for(x; x <= n; x += x & -x) {
      |         ^
street_lamps.cpp:23:90: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y <= node[x].size(); y += y & -y) {
      |                                                                                        ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int get(int, int)':
street_lamps.cpp:30:9: warning: statement has no effect [-Wunused-value]
   30 |     for(x; x; x -= x & -x) {
      |         ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:60:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:61:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:64:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:65:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 10 ms 14452 KB Output is correct
3 Correct 8 ms 14372 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 9 ms 14428 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 64300 KB Output is correct
2 Correct 690 ms 94068 KB Output is correct
3 Correct 1372 ms 159784 KB Output is correct
4 Correct 3965 ms 353944 KB Output is correct
5 Correct 3073 ms 288164 KB Output is correct
6 Correct 4403 ms 400624 KB Output is correct
7 Correct 370 ms 49428 KB Output is correct
8 Correct 151 ms 37904 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15076 KB Output is correct
2 Correct 13 ms 14932 KB Output is correct
3 Correct 15 ms 14692 KB Output is correct
4 Correct 10 ms 14420 KB Output is correct
5 Runtime error 1448 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14436 KB Output is correct
2 Correct 11 ms 14720 KB Output is correct
3 Correct 14 ms 14932 KB Output is correct
4 Correct 15 ms 15028 KB Output is correct
5 Correct 524 ms 49304 KB Output is correct
6 Correct 2624 ms 228200 KB Output is correct
7 Correct 4329 ms 399628 KB Output is correct
8 Runtime error 1167 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 10 ms 14452 KB Output is correct
3 Correct 8 ms 14372 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 9 ms 14428 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 8 ms 14428 KB Output is correct
8 Correct 474 ms 64300 KB Output is correct
9 Correct 690 ms 94068 KB Output is correct
10 Correct 1372 ms 159784 KB Output is correct
11 Correct 3965 ms 353944 KB Output is correct
12 Correct 3073 ms 288164 KB Output is correct
13 Correct 4403 ms 400624 KB Output is correct
14 Correct 370 ms 49428 KB Output is correct
15 Correct 151 ms 37904 KB Output is correct
16 Correct 14 ms 15076 KB Output is correct
17 Correct 13 ms 14932 KB Output is correct
18 Correct 15 ms 14692 KB Output is correct
19 Correct 10 ms 14420 KB Output is correct
20 Runtime error 1448 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -