제출 #170884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170884		songc	가로등 (APIO19_street_lamps)	C++14	0 / 100	138 ms	10852 KiB

street_lamps

#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;
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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);
    ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int read(int)':
street_lamps.cpp:36:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ret;
         ^~~
street_lamps.cpp: In function 'void sweep()':
street_lamps.cpp:41:28: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (it.t < 0) ans[-it.t] += read(it.y);
                 ~~~~~~~~~~~^~~~~~~~~~~~~

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