Submission #237320

#	Time	Username	Problem	Language	Result	Execution time	Memory
237320		limabeans	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	132 ms	11020 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;









int n, q;


void task1() {
    vector<int> a[105];
    auto get = [&](int l, int r, vector<int> a) {
	for (int i=l; i<r; i++) {
	    if (!a[i]) return false;
	}
	return true;
    };
    
    string s; cin>>s;
    a[0].resize(n+1);
    for (int i=1; i<=n; i++) {
	a[0][i]=(s[i-1]-'0');
    }

    a[1]=a[0];


    for (int qq=1; qq<=q; qq++) {
	string op; cin>>op;
	a[qq+1]=a[qq];
	if (op=="query") {
	    int res=0;
	    int l,r; cin>>l>>r;
	    for (int t=1; t<=qq; t++) {
		res += get(l,r,a[t]);
	    }
	    cout<<res<<"\n";
	} else {
	    //toggle
	    int i; cin>>i;
	    a[qq+1][i]=1-a[qq+1][i];
	}
    }
}

int res[maxn];
pair<int,int> upd[maxn]; //{time,on/off}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    if (n<=100 && q<=100) {
	task1();
	return 0;
    }

    //assume task2
    string s;
    cin>>s;
    for (int i=1; i<=n; i++) {
	int cur=(s[i-1]-'0');
	upd[i] = {0, cur};
    }

    for (int t=1; t<=q; t++) {
	string op;
	cin>>op;
	if (op=="query") {
	    int l,r; cin>>l>>r;
	    assert(r-l==1);
	    int cur=res[l];
	    if (upd[l].second==1) {
		cur += (t-upd[l].first);
	    }
	    cout<<cur<<"\n";
	} else {
	    int i; cin>>i;
	    int now=1-upd[i].second;
	    if (now==0) {
		res[i] += (t-upd[i].first);
	    }
	    upd[i]={t,now};
	}
    }
    

    return 0;
}

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