oj.uz

Submission #170886

# Submission time Handle Problem Language Result Execution time Memory
170886 2019-12-26T16:24:02 Z songc Street Lamps (APIO19_street_lamps) C++14
0 / 100
 139 ms 8164 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int A[303030];
bool chk[303030];
int ans[303030];

struct Sq{
	int x, y, t;
	bool operator<(const Sq &r)const{
		if (x == r.x) return y < r.y;
		return x < r.x;
	}
};
set<Sq> S;
vector<Sq> V, L;

int T[303030];

void update(int k, int v){
	while (k<=N){
		T[k] += v;
		k += k & -k;
	}
}

int read(int k){
	int ret=0;
	while (k){
		ret += T[k];
		k ^= k & -k; 
	}
	return ret;
}

void sweep(){
	for (Sq it : L){
		if (it.t < 0) ans[-it.t] += read(it.y);
		else if (it.x <= it.y){
			update(it.x, it.t);
			update(it.y+1, -it.t);
		}
		else{
			update(it.y, it.t);
			update(it.x, -it.t);
		}
	}
	for (Sq it : L){
		if (it.t < 0) continue;
		if (it.x <= it.y){
			update(it.x, -it.t);
			update(it.y+1, it.t);
		}
		else{
			update(it.y, -it.t);
			update(it.x, it.t);
		}
	}
}

void DNC(int s, int e){
	if (s >= e) return;
	int mid = (s+e)/2;
	DNC(s, mid);
	DNC(mid+1, e);
	for (int i=s; i<=mid; i++) if (V[i].t > 0){
		L.push_back((Sq){V[i].x, V[i].y, V[i].t});
		L.push_back((Sq){V[i].y+1, V[i].x, V[i].t});
	}
	for (int i=mid+1; i<=e; i++) if (V[i].t < 0) L.push_back((Sq){V[i].x, V[i].y, V[i].t});
	sort(L.begin(), L.end(), [&](Sq a, Sq b){
		if (a.x == b.x) return a.t > b.t;
		return a.x < b.x;
	});
	sweep();
	L.clear();
}

int main(){
	scanf("%d %d", &N, &Q);
	
	int s=0;
	for (int i=1; i<=N; i++){
		scanf("%1d", &A[i]);
		if (A[i] && !s) s = i;
		if (!A[i] && s) {
			S.insert((Sq){s, i-1, 0});
			s = 0;
		}
	}
	if (s) S.insert((Sq){s, N, 0});
	char str[10];
	for (int i=1; i<=Q; i++){
		scanf("%s", str+1);
		if (str[1] == 't'){
			int k;
			scanf("%d", &k);
			if (A[k]){
				auto it = --S.lower_bound((Sq){k, N+1, 0});
				Sq a = *it;
				S.erase(it);
				V.push_back((Sq){a.x, a.y, i-a.t});
				if (a.x != k) S.insert((Sq){a.x, k-1, i});
				if (a.y != k) S.insert((Sq){k+1, a.y, i});
				A[k] = 0;
			}
			else{
				auto it = S.lower_bound((Sq){k, N+1, 0});
				if (A[k-1] && A[k+1]){
					auto pr = it;
					Sq a = *it;
					Sq b = *(--pr);
					S.erase(it), S.erase(pr);
					V.push_back((Sq){a.x, a.y, i-a.t});
					V.push_back((Sq){b.x, b.y, i-b.t});
					S.insert((Sq){b.x, a.y, i});
				}
				else if (A[k-1]){
					Sq a = *(--it);
					S.erase(it);
					V.push_back((Sq){a.x, a.y, i-a.t});
					S.insert((Sq){a.x, a.y+1, i});
				}
				else if (A[k+1]){
					Sq a = *it;
					S.erase(it);
					V.push_back((Sq){a.x, a.y, i-a.t});
					S.insert((Sq){a.x-1, a.y, i});
				}
				else S.insert((Sq){k, k, i});
				A[k] = 1;
			}
		}
		else{
			int x, y;
			scanf("%d %d", &x, &y);
			y--;
			chk[i] = true;
			if (A[x]){
				auto it = --S.lower_bound((Sq){x, N+1, 0});
				if (it->y >= y) ans[i] += i - it->t;
			}
			V.push_back((Sq){x, y, -i});
		}
	}
	for (int i=1; i<=Q; i++) if (chk[i]) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%1d", &A[i]);
   ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str+1);
   ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &k);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:139:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &x, &y);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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