oj.uz

Submission #237320

# Submission time Handle Problem Language Result Execution time Memory
237320 2020-06-05T22:30:35 Z limabeans Street Lamps (APIO19_street_lamps) C++17
40 / 100
 132 ms 11020 KB 
#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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4600 KB Output is correct
2 Correct 80 ms 4964 KB Output is correct
3 Correct 90 ms 5352 KB Output is correct
4 Correct 110 ms 10252 KB Output is correct
5 Correct 108 ms 9480 KB Output is correct
6 Correct 105 ms 10120 KB Output is correct
7 Correct 124 ms 9612 KB Output is correct
8 Correct 132 ms 11020 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 75 ms 4600 KB Output is correct
9 Correct 80 ms 4964 KB Output is correct
10 Correct 90 ms 5352 KB Output is correct
11 Correct 110 ms 10252 KB Output is correct
12 Correct 108 ms 9480 KB Output is correct
13 Correct 105 ms 10120 KB Output is correct
14 Correct 124 ms 9612 KB Output is correct
15 Correct 132 ms 11020 KB Output is correct
16 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -