제출 #819702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819702		Meloric	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	610 ms	204628 KiB

rainbow

#include <bits/stdc++.h>
#define pb push_back
//#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

using namespace std;

//const int inf = 1e18;

void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}

// A = 1 - V + E - F'
//   = 1 - 2 + 6 - 3
//   = 1 - 4 + 12 - 6 
//   = 1 - 2 + 3 - 1 = 1
const int MAXQ = 100000;
const int MAXW = 200000;
//const int MAXW = 5;
//const int MAXQ = 2;

struct seg{
	array<set<int>, MAXW+5>events;
	array<int, MAXW+5> root;
	array<int, MAXQ*65> LC, RC, VAL;
	int node = 0;
	void upd(int prv, int& u, int tl, int tr, int pos, int val){
		if(tl > pos || tr < pos)return u=prv, void();
		u=++node;
		if(tl==tr)return VAL[u]=VAL[prv]+val, void();
		int tm=(tl+tr)/2;
		upd(LC[prv], LC[u], tl, tm, pos, val);
		upd(RC[prv], RC[u], tm+1, tr, pos, val);
		VAL[u] = VAL[LC[u]]+VAL[RC[u]];
	}
	int qer(int u, int tl, int tr, int l, int r){
		if(!u)return 0;
		if(tl > r || tr < l)return 0;
		if(tl >= l && tr <= r)return VAL[u];
		int tm = (tl+tr)/2;
		int ret = qer(LC[u], tl, tm, l, r)+qer(RC[u], tm+1, tr, l, r);
		return ret;
	}
	void init(){
		for(int i = 0; i< events.size(); i++){
			if(i)root[i]=root[i-1];
			for(auto e : events[i])upd(root[i], root[i], 0, MAXW+3, e, 1);
		}
	}
	int oqer(int x1, int x2, int y1, int y2){
		return -qer(root[x1-1], 0, MAXW+3, y1, y2)+qer(root[x2], 0, MAXW+3, y1, y2);
	}

}EH, EV, F, V;
int mnx=MAXW+5, mxx=0, mny=MAXW+5, mxy=0;

void add_river(int x, int y){
	mnx = min(mnx, x);
	mny = min(mny, y);
	mxx = max(mxx, x);
	mxy = max(mxy, y);
	F.events[x].insert(y);
	V.events[x].insert(y);
	V.events[x+1].insert(y);
	V.events[x].insert(y+1);
	V.events[x+1].insert(y+1);
	EH.events[x].insert(y);
	EH.events[x].insert(y+1);
	EV.events[x].insert(y);
	EV.events[x+1].insert(y);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	add_river(sc, sr);
	for(int i = 0; i< M; i++){
		if(S[i]=='N')sr--;
		if(S[i]=='E')sc++;
		if(S[i]=='S')sr++;
		if(S[i]=='W')sc--;
		add_river(sc, sr);
	}
	EH.init();
	EV.init();
	F.init();
	V.init();
}

	
int colour(int ar, int ac, int br, int bc) {
	int ret = 1;
	if(ar < mny && ac < mnx && br > mxy && bc > mxx)ret++;
	ret-=V.oqer(ac+1, bc, ar+1, br);
	ret+=EV.oqer(ac+1, bc, ar, br);
	ret+=EH.oqer(ac, bc, ar+1, br);
	ret-=F.oqer(ac, bc, ar, br);
	return ret;
}
/*
void solve(){
	int r, c, m, q; cin >> r >> c >> m >> q;
	int sr, sc; cin >> sr >> sc;
	string S; cin >> S;
	init(r, c, sr, sc, m, &S[0]);
	
	for(int i = 0; i< q; i++){
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << colour(x1, y1, x2, y2) << '\n';
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}
*/

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

rainbow.cpp:15:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 | void p(auto A){
      |        ^~~~
rainbow.cpp: In member function 'void seg::init()':
rainbow.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<std::set<int>, 200005>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i = 0; i< events.size(); i++){
      |                  ~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26