Submission #743921

#	Time	Username	Problem	Language	Result	Execution time	Memory
743921		ThMinh_	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	135 ms	5920 KiB

street_lamps

#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 (stderr)

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 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20