oj.uz

Submission #402043

# Submission time Handle Problem Language Result Execution time Memory
402043 2021-05-11T08:40:56 Z kai824 Street Lamps (APIO19_street_lamps) C++17
0 / 100
 5000 ms 524292 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
int N, Q, x, a, b, l, r;
bool A[300005];
char tmp;
string s;
set<pair<int, int> > S;
 
 
typedef gp_hash_table<int, int, hash<int>> ht;
ht ft[300005];
#define ls(x) (x&(-x))
void update(int a,int b,int upd){
  //cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
  for(;a<=N;a+=ls(a)){
    for(int x=b;x<=N;x+=ls(x)){
      if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
      else ft[a][x]+=upd;
    }
  }
}
 
inline void upd(int l1, int l2, int r1, int r2, int v) {
	// add v to (l1, r1)
	/*for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] += v;*/
  update(l1,r1,v);
	
	// add -v to (l1, r2 + 1)
  update(l1,r2+1,-v);
	
	// add -v to (l2 + 1, r1)
	update(l2+1,r1,-v);
	
	// add v to (l2 + 1, r2 + 1)
	update(l2+1,r2+1,v);
}
 
inline int qry(int x, int y) {
	int r = 0;
	for (int i = x; i; i -= ls(i))
		for (int j = y; j; j -= ls(j))
			r += ft[i][j];
	return r;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		A[i] = tmp - '0';
		if (A[i]) {
			if (i == 1 || !A[i - 1]) S.emplace(i, i);
			else {
				int lft = S.rbegin()->first;
				S.erase(--S.end());
				S.emplace(lft, i);
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cin >> s;
		if (s == "toggle") {
			cin >> x;
			if (A[x]) {
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				assert(it != S.begin());
				--it;
				l = it->first;
				r = it->second + 1;
				
				// fix S
				S.erase(it);
				if (l < x) S.emplace(l, x - 1);
				if (x < r - 1) S.emplace(x + 1, r - 1);
				
				assert(l <= x && x + 1 <= r);
				// we know that [l, x] can currently reach [x + 1, r]
				upd(l, x, x + 1, r, i);
			} else {
				vector<set<pair<int, int> >::iterator> del;
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				if (it != S.end() && it->first == x + 1) r = it->second + 1, del.push_back(it);
				else r = x + 1;
				if (it != S.begin()) {
					--it;
					if (it->second == x - 1) l = it->first, del.push_back(it);
					else l = x;
				} else l = x;
				
				// fix S
				for (auto i : del) S.erase(i);
				S.emplace(l, r - 1);
				
				// we know that [l, x] cannot currently reach [x + 1, r]
				upd(l, x, x + 1, r, -i);
			}
			A[x] ^= 1;
		} else {
			cin >> a >> b;
			auto it = S.upper_bound(make_pair(a, (int)1e9));
			if (it != S.begin()) {
				--it;
				if (b <= it->second + 1) {
					cout << qry(a, b) + i << '\n';
					goto done;
				}
			}
			cout << qry(a, b) << '\n';
			done:;
		}
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 63684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 272 ms 64700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 64032 KB Output is correct
2 Correct 87 ms 64208 KB Output is correct
3 Correct 73 ms 64280 KB Output is correct
4 Correct 67 ms 64068 KB Output is correct
5 Execution timed out 5056 ms 300504 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 64164 KB Output is correct
2 Correct 71 ms 64244 KB Output is correct
3 Correct 70 ms 64124 KB Output is correct
4 Correct 70 ms 63980 KB Output is correct
5 Runtime error 3512 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 63684 KB Output isn't correct
2 Halted 0 ms 0 KB -