oj.uz

Submission #683780

# Submission time Handle Problem Language Result Execution time Memory
683780 2023-01-19T10:49:53 Z S2speed Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 361 ms 176980 KB 
#include "rainbow.h"
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (int)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e6 + 17 , md = 1e9 + 7 , inf = 2e8;

vector<int> merge(vector<int> &a , vector<int> &b){
	vector<int> res;
	int as = sze(a) , bs = sze(b);
	a.push_back(inf); b.push_back(inf);
	int x = 0 , y = 0;
	for(int e = 0 ; e < as + bs ; e++){
		if(a[x] < b[y]){
			res.push_back(a[x++]);
		} else {
			res.push_back(b[y++]);
		}
	}
	a.pop_back(); b.pop_back();
	return res;
}

struct segtree {

	int sz = 1;
	vector<vector<int>> val;

	void init(int n){
		while(sz < n) sz <<= 1;
		val.resize(sz << 1);
		return;
	}

	void add(int i , int k , int x , int lx , int rx){
		if(rx - lx == 1){
			val[x].push_back(k);
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			add(i , k , ln , lx , m);
		} else {
			add(i , k , rn , m , rx);
		}
		return;
	}

	void add(int i , int k){
		add(i , k , 0 , 0 , sz);
		return;
	}

	void build(int x , int lx , int rx){
		if(rx - lx == 1){
			sort(all(val[x]));
			val[x].resize(distance(val[x].begin() , unique(all(val[x]))));
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(ln , lx , m); build(rn , m , rx);
		val[x] = merge(val[ln] , val[rn]);
		return;
	}

	void build(){
		build(0 , 0 , sz);
		return;
	}

	int cal(int l1 , int r1 , int l2 , int r2 , int x , int lx , int rx){
		if(rx <= l1 || lx >= r1) return 0;
		if(rx <= r1 && lx >= l1){
			int res = lower_bound(all(val[x]) , r2) - lower_bound(all(val[x]) , l2);
			return res;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		int a = cal(l1 , r1 , l2 , r2 , ln , lx , m) , b = cal(l1 , r1 , l2 , r2 , rn , m , rx);
		return a + b;
	}

	int cal(int l1 , int r1 , int l2 , int r2){
		return cal(l1 , r1 , l2 , r2 , 0 , 0 , sz);
	}

};

segtree v , e[2] , f;

void add(int x , int y){
	v.add(x , y);
	e[0].add(x - 1 , y); e[0].add(x , y);
	e[1].add(x , y - 1); e[1].add(x , y);
	f.add(x - 1 , y - 1); f.add(x - 1 , y); f.add(x , y - 1); f.add(x , y);
	return;
}

void init(int n , int m , int sx , int sy , int k , char *s){
	v.init(n + 1); e[0].init(n + 1); e[1].init(n + 1); f.init(n + 1);
	int x = sx , y = sy;
	for(int i = 0 ; ; i++){
		add(x , y);
		if(i == k) break;
		if(s[i] == 'N'){
			x--;
		} else if(s[i] == 'S'){
			x++;
		} else if(s[i] == 'E'){
			y++;
		} else {
			y--;
		}
	}
	v.build(); e[0].build(); e[1].build(); f.build();
	return;
}

int colour(int l1 , int l2 , int r1 , int r2){
	r1++; r2++;
	ll V = 1ll * (r1 - l1) * (r2 - l2) - v.cal(l1 , r1 , l2 , r2);
	ll E = 1ll * (r1 - l1) * (r2 - l2 - 1) + 1ll * (r1 - l1 - 1) * (r2 - l2);
	E -= e[0].cal(l1 , r1 - 1 , l2 , r2) + e[1].cal(l1 , r1 , l2 , r2 - 1);
	ll F = 1ll * (r1 - l1 - 1) * (r2 - l2 - 1) - f.cal(l1 , r1 - 1 , l2 , r2 - 1) + 1;
    return V - E + F - 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Incorrect 2 ms 340 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 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 104 ms 9980 KB Output is correct
4 Correct 138 ms 13964 KB Output is correct
5 Correct 158 ms 13776 KB Output is correct
6 Correct 112 ms 12616 KB Output is correct
7 Correct 130 ms 12636 KB Output is correct
8 Correct 76 ms 8436 KB Output is correct
9 Correct 157 ms 13780 KB Output is correct
10 Correct 146 ms 13768 KB Output is correct
11 Correct 126 ms 12612 KB Output is correct
12 Correct 90 ms 13372 KB Output is correct
13 Correct 109 ms 13644 KB Output is correct
14 Correct 84 ms 13716 KB Output is correct
15 Correct 86 ms 12792 KB Output is correct
16 Correct 105 ms 11312 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 277 ms 162240 KB Output is correct
3 Correct 357 ms 176980 KB Output is correct
4 Correct 361 ms 171408 KB Output is correct
5 Correct 321 ms 158664 KB Output is correct
6 Correct 287 ms 129808 KB Output is correct
7 Incorrect 267 ms 137820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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