oj.uz

Submission #118411

# Submission time Handle Problem Language Result Execution time Memory
118411 2019-06-19T01:00:58 Z tmwilliamlin168 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 531 ms 205816 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5, mxSTS=(6e5+9)*19+1;
int sts, st[mxSTS], lc[mxSTS], rc[mxSTS];

struct dat {
	set<int> ta[mxN+1];
	int rt[mxN+2];
	void a(array<int, 2> a) {
		ta[a[0]].insert(a[1]);
	}
	void bld() {
		for(int i=0; i<=mxN; ++i) {
			rt[i+1]=rt[i];
			for(int j : ta[i])
				upd(j, rt[i+1]);
		}
	}
	void upd(int l1, int &i, int l2=0, int r2=mxN) {
		st[sts]=st[i]+1;
		lc[sts]=lc[i];
		rc[sts]=rc[i];
		i=sts++;
		if(l2==r2)
			return;
		int m2=(l2+r2)/2;
		if(l1<=m2)
			upd(l1, lc[i], l2, m2);
		else
			upd(l1, rc[i], m2+1, r2);
	}
	int qry(int l1, int r1, int l2, int r2) {
		return l2>r2?0:qry(l2, r2, rt[r1+1], 0, mxN)-qry(l2, r2, rt[l1], 0, mxN);
	}
	int qry(int l1, int r1, int i, int l2, int r2) {
		if(l1<=l2&&r2<=r1)
			return st[i];
		int m2=(l2+r2)/2;
		return (l1<=m2?qry(l1, r1, lc[i], l2, m2):0)+(m2<r1?qry(l1, r1, rc[i], m2+1, r2):0);
	}
} sv, ser, sec, ss;

void init(int r, int c, int sr, int sc, int m, char *s) {
	set<array<int, 2>> cs{{--sr, --sc}};
	for(int i=0; i<m; ++i) {
		if(s[i]=='N')
			--sr;
		else if(s[i]=='S')
			++sr;
		else if(s[i]=='E')
			++sc;
		else
			--sc;
		cs.insert({sr, sc});
	}
	for(auto a : cs) {
		sv.a(a);
		sv.a({a[0], a[1]+1});
		sv.a({a[0]+1, a[1]});
		sv.a({a[0]+1, a[1]+1});
		ser.a(a);
		ser.a({a[0]+1, a[1]});
		sec.a(a);
		sec.a({a[0], a[1]+1});
		ss.a(a);
	}
	sv.bld();
	ser.bld();
	sec.bld();
	ss.bld();
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac, --br, --bc;
	int e=2*(br-ar+bc-ac+2)+ser.qry(ar+1, br, ac, bc)+sec.qry(ar, br, ac+1, bc);
	int v=2*(br-ar+bc-ac+2)+sv.qry(ar+1, br, ac+1, bc);
	int s=ss.qry(ar, br, ac, bc);
	int c=!sv.qry(ar+1, br, ac+1, bc)||ser.qry(ar+1, br, ac, bc)-ser.qry(ar+1, br, ac+1, bc-1)||sec.qry(ar, br, ac+1, bc)-sec.qry(ar+1, br-1, ac+1, bc)?1:2;
    return e-v+c-s;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 41336 KB Output is correct
2 Correct 46 ms 42360 KB Output is correct
3 Incorrect 45 ms 41340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 41080 KB Output is correct
2 Incorrect 41 ms 41080 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 41080 KB Output is correct
2 Correct 531 ms 205788 KB Output is correct
3 Correct 282 ms 205688 KB Output is correct
4 Correct 307 ms 205816 KB Output is correct
5 Correct 275 ms 164572 KB Output is correct
6 Correct 112 ms 72440 KB Output is correct
7 Incorrect 196 ms 103160 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 41336 KB Output is correct
2 Correct 46 ms 42360 KB Output is correct
3 Incorrect 45 ms 41340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 41336 KB Output is correct
2 Correct 46 ms 42360 KB Output is correct
3 Incorrect 45 ms 41340 KB Output isn't correct
4 Halted 0 ms 0 KB -