QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#863135#3149. Territoryfryan0 0ms0kbC++203.0kb2025-01-19 13:32:392025-01-19 13:32:39

Judging History

This is the latest submission verdict.

  • [2025-01-19 13:32:39]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2025-01-19 13:32:39]
  • Submitted

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long
#define A array<int,2>

const int mod = 998244353;

int n,k,ans=0;
string s;

int dx,dy,cx,cy;
set<A> pt;

map<A,set<A>> iv;

void intersect(set<A> &a, set<A> &b, set<A> &c, set<A> &d, int av, int bv, int cv, int dv) {
	assert(sz(a) && sz(b) && sz(c) && sz(d));
	auto ia = a.begin(), ib = b.begin(), ic = c.begin(), id = d.begin();
	int cnt = 0;
	while (ia != a.end() && ib != b.end() && ic != c.end() && id != d.end()) {
		auto [la,ra] = *ia; la += av, ra += av;
		auto [lb,rb] = *ib; lb += bv, rb += bv;
		auto [lc,rc] = *ic; lc += cv, rc += cv;
		auto [ld,rd] = *id; ld += dv, rd += dv;
		
		int tl = max(max(la,lb),max(lc,ld));
		int tr = min(min(ra,rb),min(rc,rd));
		
		ans += max(0ll,tr-tl+1);
		cnt += max(0ll,tr-tl+1);
		if (ra==tr) {
			ia = next(ia);
		}
		if (rb==tr) {
			ib = next(ib);
		}
		if (rc==tr) {
			ic = next(ic);
		}
		if (rd==tr) {
			id = next(id);
		}
	}
//	cout<<cnt<<"\n";
}

A F(A a) {
	auto [x,y] = a;
	int rem = x/dx;
	return {x-rem*dx,y-rem*dy};
}

void print(A a) {
	cout<<a[0]<<","<<a[1]<<"  ";
}

void print(set<array<int,2>> &s) {
	for (auto [l,r] : s) cout<<l<<".."<<" "<<r<<"  ";
	cout<<"\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin>>n>>k>>s;
	
	
	for (int i=0; i<n; i++) {
		pt.insert({dx,dy});
		if (s[i]=='N') {dy++;}
		else if (s[i]=='S') {dy--;}
		else if (s[i]=='E') {dx++;}
		else if (s[i]=='W') {dx--;}
		pt.insert({dx,dy});
	}
	
	int xm = dx/abs(dx);
	int ym = dy/abs(dy);
	int ad = 100000000;
	
	dx *= xm; dy *= ym;
	
//	print(F({0,0}));
	
//	return 0;
	
	set<array<int,2>> npt;
	
	for (auto [x,y] : pt) {
		int x1=x,y1=y;
		x1 *= xm; y1 *= ym;
		x1 += ad; y1 += ad;
		npt.insert({x1,y1});
	}
	pt = npt;
	
	for (auto [x,y] : pt) {
		int rem = x/dx;
	//	cout<<x<<" "<<y<<": "<<rem<<" "<<rem+k-1<<"\n";
		iv[{x-rem*dx,y-rem*dy}].insert({rem,rem+k-1});
	}
	
	//collapse intervals
	for (auto &[k,s] : iv) {
		set<A> ns;
		auto [pl,pr] = *(s.begin());
		for (auto [cl,cr] : s) {
			if (cl > pr) {
				ns.insert({pl,pr});
				pl = cl;
			}
			pr = cr;
		}
		ns.insert({pl,pr});
		s = ns;
	}
	
	//do some comparisons
	for (auto [k,s] : iv) {
		auto [x,y] = k;
//		if (x != 1 || y != -1) continue;
//		cout<<x<<" "<<y<<"\n";
		int av = 0;
		int bv = (x+1)/dx; bv = -bv;
		int cv = x/dx; cv = -cv;
		int dv = (x+1)/dx; dv = -dv;
		if (iv.count(F({x+1,y})) &&
			iv.count(F({x,y+1})) && 
			iv.count(F({x+1,y+1}))) {
/*				print(k);
				print(F({x+1,y}));
				print(F({x,y+1}));
				print(F({x+1,y+1}));
				cout<<"\n\n";
				print(s);
				print(iv[F({x+1,y})]);
				print(iv[F({x,y+1})]);
				print(iv[F({x+1,y+1})]);
				cout<<av<<" "<<bv<<" "<<cv<<" "<<dv<<"\n";
*/				intersect(s,iv[F({x+1,y})],iv[F({x,y+1})],iv[F({x+1,y+1})],av,bv,cv,dv);
//				cout<<"\n";
			}
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

5 1
SSWEN

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%