oj.uz

Submission #819601

# Submission time Handle Problem Language Result Execution time Memory
819601 2023-08-10T12:03:07 Z Meloric Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 449 ms 206676 KB 
#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 

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;

void add_river(int x, int 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;
	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();
}*/

Compilation message

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41296 KB Output is correct
2 Correct 29 ms 42400 KB Output is correct
3 Incorrect 27 ms 41300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41012 KB Output is correct
2 Correct 22 ms 41016 KB Output is correct
3 Correct 299 ms 141160 KB Output is correct
4 Correct 405 ms 206624 KB Output is correct
5 Correct 442 ms 205388 KB Output is correct
6 Correct 337 ms 168376 KB Output is correct
7 Correct 409 ms 166244 KB Output is correct
8 Correct 98 ms 44728 KB Output is correct
9 Correct 438 ms 206676 KB Output is correct
10 Correct 449 ms 205356 KB Output is correct
11 Correct 378 ms 168444 KB Output is correct
12 Correct 229 ms 195168 KB Output is correct
13 Correct 237 ms 206556 KB Output is correct
14 Correct 244 ms 205392 KB Output is correct
15 Correct 243 ms 168508 KB Output is correct
16 Correct 328 ms 159064 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41052 KB Output is correct
2 Correct 171 ms 200948 KB Output is correct
3 Correct 315 ms 201124 KB Output is correct
4 Correct 227 ms 201092 KB Output is correct
5 Correct 203 ms 160508 KB Output is correct
6 Correct 93 ms 71112 KB Output is correct
7 Incorrect 139 ms 100832 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41296 KB Output is correct
2 Correct 29 ms 42400 KB Output is correct
3 Incorrect 27 ms 41300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41296 KB Output is correct
2 Correct 29 ms 42400 KB Output is correct
3 Incorrect 27 ms 41300 KB Output isn't correct
4 Halted 0 ms 0 KB -