oj.uz

Submission #739163

# Submission time Handle Problem Language Result Execution time Memory
739163 2023-05-10T05:13:13 Z nguyentunglam Street Lamps (APIO19_street_lamps) C++17
40 / 100
 4100 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) {
        if (node[x].empty()) continue;
        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);
            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: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.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:62:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
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".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:66:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 64864 KB Output is correct
2 Correct 678 ms 91160 KB Output is correct
3 Correct 1373 ms 156684 KB Output is correct
4 Correct 3558 ms 349376 KB Output is correct
5 Correct 2980 ms 283416 KB Output is correct
6 Correct 4078 ms 395972 KB Output is correct
7 Correct 335 ms 43716 KB Output is correct
8 Correct 125 ms 32180 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15080 KB Output is correct
2 Correct 11 ms 14932 KB Output is correct
3 Correct 10 ms 14728 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Runtime error 1256 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 9 ms 14420 KB Output is correct
2 Correct 10 ms 14704 KB Output is correct
3 Correct 11 ms 14932 KB Output is correct
4 Correct 13 ms 15060 KB Output is correct
5 Correct 411 ms 43452 KB Output is correct
6 Correct 2250 ms 222796 KB Output is correct
7 Correct 4100 ms 394868 KB Output is correct
8 Runtime error 1129 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 9 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 451 ms 64864 KB Output is correct
9 Correct 678 ms 91160 KB Output is correct
10 Correct 1373 ms 156684 KB Output is correct
11 Correct 3558 ms 349376 KB Output is correct
12 Correct 2980 ms 283416 KB Output is correct
13 Correct 4078 ms 395972 KB Output is correct
14 Correct 335 ms 43716 KB Output is correct
15 Correct 125 ms 32180 KB Output is correct
16 Correct 13 ms 15080 KB Output is correct
17 Correct 11 ms 14932 KB Output is correct
18 Correct 10 ms 14728 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Runtime error 1256 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -