oj.uz

Submission #743921

# Submission time Handle Problem Language Result Execution time Memory
743921 2023-05-18T06:12:22 Z ThMinh_ Street Lamps (APIO19_street_lamps) C++14
20 / 100
 135 ms 5920 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;
        }
    }
    st.insert({-1, -1});
    st.insert({1e9, 1e9});
    forin(j,1,q) {
        string s; cin>>s;
        if(s[0] == 't') {
            int i; cin>>i;
            auto i1 = st.upper_bound({i, 1e9});
            auto i2 = i1--;
            pair<int, int> cur = *i1;
            pair<int, int> aft = *i2;
//            cout<<cur.fi<<" "<<cur.la<<"\n";
//            cout<<aft.fi<<" "<<aft.la<<"\n";
            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(cur.fi != cur.la) {
                    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});
//            cout<<it.fi<<" "<<it.la<<"\n";
            if(it.fi <= a && b <= it.la + 1) cout<<get(a, b) - (q - j)<<"\n";
            else cout<<get(a, b)<<"\n";
        }
//        forin(i,1,n + 1) {
//            forin(j,1,n + 1) cout<<get(i, j)<<" ";
//            cout<<"\n";
//        }
//        for(auto [f, l] : st) cout<<f<<"."<<l<<" "; cout<<"\n";
//        if(j == 4) return 0;
    }
}

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

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4840 KB Output is correct
2 Correct 135 ms 5920 KB Output is correct
3 Runtime error 2 ms 596 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 2 ms 3284 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Runtime error 3 ms 2428 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 3 ms 2516 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 3 ms 3280 KB Output is correct
4 Correct 2 ms 3440 KB Output is correct
5 Runtime error 3 ms 2432 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 121 ms 4840 KB Output is correct
9 Correct 135 ms 5920 KB Output is correct
10 Runtime error 2 ms 596 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -