Submission #1126117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126117		luvna	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	980 ms	56192 KiB

street_lamps

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 1e6 + 15;

int n, q;
int a[N];

namespace subtask1{
    bool check(void){
        return n <= 100 && q <= 100;
    }

    int type[N], l[N], r[N];
    int b[N];

    void main(){
        for(int i = 1; i <= q; i++){
            string s; cin >> s;
            type[i] = (s == "toggle" ? 0 : 1);
            if(!type[i]){
                cin >> l[i];
            }
            else{
                cin >> l[i] >> r[i];
                for(int j = 1; j <= n; j++) b[j] = a[j];
                int ans = 0;
                for(int j = 0; j < i; j++){
                    if(j > 0 && !type[j]) b[l[j]] ^= 1;
                    bool ok = true;
                    for(int k = l[i]; k < r[i]; k++) ok &= b[k];
                    ans += ok;
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask5{

    struct event{
        int l, r, t, k;
        event() : l(0), r(0), t(0), k(0) {}
        event(int l, int r, int t, int k) : l(l), r(r), t(t), k(k) {}

        bool operator <(const event& a) const{
            return l < a.l;
        }
    };

    int m;
    vector<event> evt;
    set<pair<int,int>> blocks;
    ll ans[N];
    ll bit[N];

    void update(int idx, int v){
        for(;idx < N; idx += (idx & (-idx))) bit[idx] += v;
    }

    ll get(int l, int r){ll res = 0; l--;
        for(;r; r -= (r & (-r))) res += bit[r];
        for(;l; l -= (l & (-l))) res -= bit[l];
        return res;
    }

    stack<pair<int,int>> st;

    void cdq(int l, int r){
        if(l >= r) return;

        int mid = (l+r) >> 1;

        vector<event> upd, ask;

        for(int i = l; i <= mid; i++) if(!evt[i].t) upd.push_back(evt[i]);
        for(int i = mid+1; i <= r; i++) if(evt[i].t) ask.push_back(evt[i]);

        sort(all(upd));
        sort(all(ask));

        for(int i = 0, j = 0; i < sz(ask); i++){
            while(j < sz(upd) && upd[j].l <= ask[i].l){
                update(upd[j].r, upd[j].k);
                st.push(pii(upd[j].r, -upd[j].k));
                j++;
            }

            ans[ask[i].k] +=  get(ask[i].r, N-1);
        }

        while(!st.empty()) update(st.top().fi, st.top().se), st.pop();

        cdq(l,mid);
        cdq(mid+1,r);
    }

    void main(){
        vector<pair<int, int>> base;

        for(int i = 1; i <= n+1; i++){
            if(i == 1) base.push_back(pii(i,i));
            else if(a[i-1]) base.back().se = i;
            else base.push_back(pii(i,i));
        }

        for(auto [l, r] : base){
            blocks.insert(pii(l,r));
            evt.push_back(event(l,r,0,q));
        }

        for(int i = 1; i <= q; i++){
            string t; cin >> t;
            if(t == "toggle"){
                int p; cin >> p;
                auto id = blocks.upper_bound(pii(p,N));
                id--;
                int l = (*id).fi, r = (*id).se;
                evt.push_back(event(l,r,0,-(q-i)));
                if(a[p]){
                    blocks.erase(id);
                    blocks.insert(pii(l,p));
                    blocks.insert(pii(p+1,r));
                    evt.push_back(event(l,p,0,q-i));
                    evt.push_back(event(p+1,r,0,q-i));
                }
                else{
                    auto nxt_id = id;
                    nxt_id++;
                    if(nxt_id != blocks.end()){
                        int L = l;
                        int R = (*nxt_id).se;
                        blocks.erase(id);
                        blocks.erase(nxt_id);
                        evt.push_back(event(p+1,R,0,-(q-i)));
                        blocks.insert(pii(L,R));
                        evt.push_back(event(L,R,0,q-i));
                    }
                }
                a[p] ^= 1;
            }
            else{
                int l, r; cin >> l >> r;
                evt.push_back(event(l,r,1,++m));
                auto id = blocks.upper_bound(pii(l,N));
                id--;
                if((*id).se >= r){
                    ans[m] = -(q - i);
                }
            }
        }

        cdq(0,sz(evt)-1);

        for(int i = 1; i <= m; i++) cout << ans[i] << endl;
    }
}

void solve(){
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        char x; cin >> x;
        a[i] = x - '0';
    }

    if(subtask1::check()) subtask1::main();
    else subtask5::main();
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20