oj.uz

Submission #118278

# Submission time Handle Problem Language Result Execution time Memory
118278 2019-06-18T14:32:19 Z tmwilliamlin168 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1229 ms 78412 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5, mxSTS=1e5*19+1;

struct pst {
	vector<int> ta[mxN];
	int rt[mxN+1], sts=1, st[mxSTS], lc[mxSTS], rc[mxSTS];
	void a(array<int, 2> a) {
		ta[a[0]].push_back(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-1) {
		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-1)-qry(l2, r2, rt[l1], 0, mxN-1);
	}
	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);
	}
} stv, ster, stec, sts;

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) {
		stv.a(a);
		if(cs.find({a[0], a[1]+1})!=cs.end())
			ster.a(a);
		if(cs.find({a[0]+1, a[1]})!=cs.end())
			stec.a(a);
		if(cs.find({a[0], a[1]+1})!=cs.end()&&cs.find({a[0]+1, a[1]})!=cs.end()&&cs.find({a[0]+1, a[1]+1})!=cs.end())
			sts.a(a);
	}
	stv.bld();
	ster.bld();
	stec.bld();
	sts.bld();
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac, --br, --bc;
	int e=2*(br-ar+bc-ac+4)+ster.qry(ar, br, ac, bc-1)+stec.qry(ar, br-1, ac, bc)+stv.qry(ar, ar, ac, bc)+stv.qry(br, br, ac, bc)+stv.qry(ar, br, ac, ac)+stv.qry(ar, br, bc, bc);
	int v=2*(br-ar+bc-ac+4)+stv.qry(ar, br, ac, bc);
	int c=!stv.qry(ar, br, ac, bc)||stv.qry(ar, br, ac, bc)-stv.qry(ar+1, br-1, ac+1, bc-1)?1:2;
	int s=stv.qry(ar, ar, ac, ac)+stv.qry(ar, ar, bc, bc)+stv.qry(br, br, ac, ac)+stv.qry(br, br, bc, bc)+ster.qry(ar, ar, ac, bc-1)+ster.qry(br, br, ac, bc-1)+stec.qry(ar, br-1, ac, ac)+stec.qry(ar, br-1, bc, bc)+sts.qry(ar, br-1, ac, bc-1);
    return e-v+c-s;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 22528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22400 KB Output is correct
2 Correct 23 ms 22272 KB Output is correct
3 Correct 774 ms 55748 KB Output is correct
4 Correct 1229 ms 75720 KB Output is correct
5 Correct 1044 ms 76232 KB Output is correct
6 Correct 965 ms 78412 KB Output is correct
7 Correct 1014 ms 63488 KB Output is correct
8 Correct 628 ms 26204 KB Output is correct
9 Correct 1018 ms 75676 KB Output is correct
10 Correct 1076 ms 75808 KB Output is correct
11 Correct 1050 ms 78240 KB Output is correct
12 Correct 354 ms 72096 KB Output is correct
13 Correct 363 ms 75532 KB Output is correct
14 Correct 374 ms 75960 KB Output is correct
15 Correct 372 ms 78320 KB Output is correct
16 Correct 838 ms 60988 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22264 KB Output is correct
2 Correct 165 ms 72080 KB Output is correct
3 Correct 141 ms 75640 KB Output is correct
4 Correct 151 ms 75764 KB Output is correct
5 Correct 113 ms 61452 KB Output is correct
6 Correct 69 ms 43128 KB Output is correct
7 Incorrect 110 ms 63580 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 22528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 22528 KB Output isn't correct
2 Halted 0 ms 0 KB -