QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863135 | #3149. Territory | fryan | 0 | 0ms | 0kb | C++20 | 3.0kb | 2025-01-19 13:32:39 | 2025-01-19 13:32:39 |
Judging History
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;
}
詳細信息
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%