oj.uz

답안 #743835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743835 2023-05-18T04:29:13 Z ThMinh_ 가로등 (APIO19_street_lamps) C++14
0 / 100
 5 ms 4692 KB 
#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
#define fi first
#define la second
using namespace std;
const int N = 1e3 + 10;
int n, q;
int tr[N][N], flag[N][N];
bool a[N];
set<pair<int, int>> st;
void up(int f, int l, int val) {
    while(f <= n + 1) {
        int x = l;
        while(x) {
            tr[f][x] += val;
            x -= x & -x;
        }
        f += f & -f;
    }
}
int get(int f, int l) {
    int res = 0;
    while(f) {
        int x = l;
        while(x <= n + 1) {
            res += tr[f][x];
            x += x & -x;
        }
        f -= f & -f;
    }
    return res;
}
void add(int f, int l, int val) {
    up(f, l + 1, val);
    st.insert({f, l});
}
int 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>>q;
    string s; cin>>s;
    s = " " + s;
    forin(i,1,n) a[i] = (s[i] == '1');
    int f = -1;
    forin(i,1,n + 1) {
        if(f == -1 && a[i]) f = i;
        if(f != -1 && !a[i]) {
            add(f, i - 1, q);
            f = -1;
        }
    }
    forin(j,1,q) {
        string s; cin>>s;
        if(s[0] == 't') {
            int i; cin>>i;
            a[i] = 1 - a[i];
            auto i1 = st.upper_bound({i, 1e9});
            auto i2 = i1--;
            pair<int, int> cur = *i1;
            pair<int, int> aft = *i2;
            int val = q - j;
            if(cur.la + 1 < i && i < aft.fi - 1) add(i, i, val);
            else if(i == cur.la + 1 && i == aft.fi - 1) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                st.erase(i2); up(aft.fi, aft.la + 1, -val);
                add(cur.fi, aft.la, val);
            }
            else if(i == cur.la + 1) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                add(cur.fi, cur.la + 1, val);
            }
            else if(i == aft.fi - 1) {
                st.erase(i2); up(aft.fi, aft.la + 1, -val);
                add(aft.fi - 1, aft.la, val);
            }
            else if(i <= cur.la) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                if(i == cur.fi) add(cur.fi + 1, cur.la, val);
                else if(i == cur.la) add(cur.fi, cur.la - 1, val);
                else {
                    add(cur.fi, i - 1, val);
                    add(i + 1, cur.la, val);
                }
            }
        }
        else {
            int a, b; cin>>a>>b;
            pair<int, int> it = *--st.upper_bound({a, 1e9});
            if(b <= it.la + 1) cout<<get(a, b) - (q - j)<<"\n";
            else cout<<get(a, b)<<"\n";
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("Task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("WA.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Runtime error 5 ms 4692 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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