oj.uz

답안 #404807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404807 2021-05-15T04:11:37 Z danielcm585 가로등 (APIO19_street_lamps) C++17
0 / 100
 5000 ms 64392 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 3e5;
const int INF = 1e9;
int n, q;
int a[N+2];
gp_hash_table<int,int> bit[N+2];

void update(int r1, int r2, int c1, int c2, int v) {
    for (int i = r1; i <= n+1; i += i&-i) {
        for (int j = c1; j <= n+1; j += j&-j) {
            bit[i][j] += v;
        }
    }
    for (int i = r1; i <= n+1; i += i&-i) {
        for (int j = c2+1; j <= n+1; j += j&-j) {
            bit[i][j] -= v;
        }
    }
    for (int i = r2+1; i <= n+1; i += i&-i) {
        for (int j = c1; j <= n+1; j += j&-j) {
            bit[i][j] -= v;
        }
    }
    for (int i = r2+1; i <= n+1; i += i&-i) {
        for (int j = c2+1; j <= n+1; j += j&-j) {
            bit[i][j] += v;
        }
    }
}

int query(int r, int c) {
    int ret = 0;
    for (int i = r; i; i -= i&-i) {
        for (int j = c; j; j -= j&-j) {
            if (bit[i].find(j) != bit[i].end()) ret += bit[i][j];
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    set<ii> st;
    for (int i = 1; i <= n; i++) {
        char x; cin >> x;
        a[i] = x-'0';
        if (a[i]) {
            if (i == 1 || !a[i-1]) st.insert(ii(i,i));
            else {
                auto it = st.end(); it--;
                int l = it->fi;
                st.erase(it);
                st.insert(ii(l,i));
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        string s; cin >> s;
        if (s == "toggle") {
            int x; cin >> x;
            if (a[x]) {
                auto it = st.upper_bound(ii(x,INF)); it--;
                int l = it->fi, r = it->se;
                st.erase(it);
                if (l <= x-1) st.insert(ii(l,x-1));
                if (x+1 <= r) st.insert(ii(x+1,r));
                update(l,x,x+1,r,i);
            }
            else {
                vector<set<ii>::iterator> del;
                auto it = st.upper_bound(ii(x,INF));
                int l, r;
                if (it != st.end() && it->fi == x+1) {
                    r = it->se+1;
                    del.push_back(it);
                }
                if (it != st.begin()) {
                    it--;
                    if (it->se == x-1) {
                        l = it->fi;
                        del.push_back(it);
                    }
                    else l = x;
                }
                for (auto i : del) st.erase(i);
                st.insert(ii(l,r-1));
                update(l,x,x+1,r,-i);
            }
            a[x] ^= 1;
        }
        else {
            int a, b; cin >> a >> b;
            int ans = query(a,b);
            auto it = st.upper_bound(ii(a,INF));
            if (it != st.begin()) {
                it--;
                if (it->se+1 >= b) ans += i;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:98:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |                 update(l,x,x+1,r,-i);
      |                 ~~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:97:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |                 st.insert(ii(l,r-1));
      |                                ~^~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5087 ms 63684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5089 ms 63684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 64392 KB Output is correct
2 Incorrect 75 ms 64264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 63736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5087 ms 63684 KB Time limit exceeded
2 Halted 0 ms 0 KB -