oj.uz

답안 #402046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402046 2021-05-11T08:41:50 Z kai824 가로등 (APIO19_street_lamps) C++17
40 / 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+1;a+=ls(a)){
    for(int x=b;x<=N+1;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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 63684 KB Output is correct
2 Correct 64 ms 63640 KB Output is correct
3 Correct 66 ms 63664 KB Output is correct
4 Correct 65 ms 63664 KB Output is correct
5 Correct 65 ms 63648 KB Output is correct
6 Correct 69 ms 63648 KB Output is correct
7 Correct 73 ms 63716 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 65108 KB Output is correct
2 Correct 392 ms 65216 KB Output is correct
3 Correct 791 ms 70652 KB Output is correct
4 Correct 3723 ms 306848 KB Output is correct
5 Correct 3643 ms 309804 KB Output is correct
6 Correct 3569 ms 315496 KB Output is correct
7 Correct 1559 ms 182996 KB Output is correct
8 Correct 1599 ms 184756 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 64068 KB Output is correct
2 Correct 77 ms 64132 KB Output is correct
3 Correct 74 ms 64264 KB Output is correct
4 Correct 73 ms 64064 KB Output is correct
5 Execution timed out 5088 ms 305696 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 64196 KB Output is correct
2 Correct 73 ms 64192 KB Output is correct
3 Correct 74 ms 64216 KB Output is correct
4 Correct 75 ms 64084 KB Output is correct
5 Runtime error 3426 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 63684 KB Output is correct
2 Correct 64 ms 63640 KB Output is correct
3 Correct 66 ms 63664 KB Output is correct
4 Correct 65 ms 63664 KB Output is correct
5 Correct 65 ms 63648 KB Output is correct
6 Correct 69 ms 63648 KB Output is correct
7 Correct 73 ms 63716 KB Output is correct
8 Correct 295 ms 65108 KB Output is correct
9 Correct 392 ms 65216 KB Output is correct
10 Correct 791 ms 70652 KB Output is correct
11 Correct 3723 ms 306848 KB Output is correct
12 Correct 3643 ms 309804 KB Output is correct
13 Correct 3569 ms 315496 KB Output is correct
14 Correct 1559 ms 182996 KB Output is correct
15 Correct 1599 ms 184756 KB Output is correct
16 Correct 73 ms 64068 KB Output is correct
17 Correct 77 ms 64132 KB Output is correct
18 Correct 74 ms 64264 KB Output is correct
19 Correct 73 ms 64064 KB Output is correct
20 Execution timed out 5088 ms 305696 KB Time limit exceeded
21 Halted 0 ms 0 KB -