| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594120 |
2022-07-12T06:43:26 Z |
Cross_Ratio |
None (JOI16_ho_t4) |
C++14 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int INF = 1e18;
map<P,set<int>> M;
int dx, dy;
P r(int x, int y) {
int rx = (x%dx+dx)%dx;
int ry = y - dy * (x-rx)/dx;
return P(rx, ry);
}
int mx[4] = {0,0,1,1};
int my[4] = {0,1,1,0};
void print(priority_queue<P,vector<P>,greater<P>> PQ) {
while(!PQ.empty()) {
cout << PQ.top().first << ' ' <<PQ.top().second << '\n';
PQ.pop();
}
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
int K;
cin >> N >> K;
string s;
cin >> s;
int i, j;
int x = 0, y = 0;
set<P> S;
S.insert(P(0,0));
for(i=0;i<N;i++) {
if(s[i]=='E') x++;
if(s[i]=='W') x--;
if(s[i]=='N') y++;
if(s[i]=='S') y--;
S.insert(P(x,y));
}
int ans = 0;
for(P k : S) {
int x = k.first, y = k.second;
if(S.find(P(x,y+1))!=S.end()&&S.find(P(x+1,y))!=S.end()&&S.find(P(x+1,y+1))!=S.end()) {
ans++;
}
}
if(x==0&&y==0) cout << ans;
dx = x, dy = y;
if(dx==0) {
swap(dx, dy);
for(i=0;i<N;i++) {
if(s[i]=='E') s[i]='N';
else if(s[i]=='N') s[i]='E';
else if(s[i]=='W') s[i]='S';
else if(s[i]=='S') s[i]='W';
}
}
if(dx<0) {
dx *= -1;
for(i=0;i<N;i++) {
if(s[i]=='E') s[i]='W';
else if(s[i]=='W') s[i]='E';
}
}
assert(dx>0);
x = y = 0;
M[P(0,0)].insert(0);
for(i=0;i<N;i++) {
if(s[i]=='E') x++;
if(s[i]=='W') x--;
if(s[i]=='N') y++;
if(s[i]=='S') y--;
int rx = (x%dx+dx)%dx;
int ry = y - dy * (x-rx)/dx;
M[r(x, y)].insert((x-rx)/dx);
}
/*cout << dx << ' ' << dy << '\n';
cout << s << '\n';
for(auto it = M.begin();it!=M.end();it++) {
cout << it->first.first << ' ' << it->first.second << " :\n";
for(int m : it->second) cout << m << ' ';
cout << '\n';
}*/
S = set<P> {};
x = y = 0;
S.insert(r(x,y));
S.insert(r(x,y-1));
S.insert(r(x-1,y-1));
S.insert(r(x-1,y));
for(i=0;i<N;i++) {
if(s[i]=='E') x++;
if(s[i]=='W') x--;
if(s[i]=='N') y++;
if(s[i]=='S') y--;
int rx = (x%dx+dx)%dx;
int ry = y - dy * (x-rx) / dx;
S.insert(r(x,y));
S.insert(r(x,y-1));
S.insert(r(x-1,y-1));
S.insert(r(x-1,y));
}
ans = 0;
for(P k : S) {
int x = k.first, y = k.second;
//cout << x << ' ' << y << " How Many?\n";
priority_queue<P,vector<P>,greater<P>> res;
bool isPos=true;
for(i=0;i<4;i++) {
priority_queue<P,vector<P>,greater<P>> Rang;
int x2 = x + mx[i];
int y2 = y + my[i];
//cout << x2 << ' ' << y2 << '\n';
int z = 0;
if(x2==dx) {
x2 = 0;
y2 -= dy;
z = -1;
}
if(!M.count(P(x2,y2))) {
isPos = false;
break;
}
for(int j : M[P(x2,y2)]) {
//cout << j << ' ';
Rang.push(P(j+z,j+K-1+z));
}
//cout << '\n';
//cout << "Current Res : \n";
//print(res);
//cout << "Now Rang :\n";
//print(Rang);
priority_queue<P,vector<P>,greater<P>> Res;
int st = INF;
int en = -INF;
priority_queue<P,vector<P>,greater<P>> rang;
while(!Rang.empty()) {
if(st==INF) {
st = Rang.top().first;
en = st;
}
if(Rang.top().first<=en) {
en = max(en, Rang.top().second);
Rang.pop();
}
else {
rang.push(P(st,en));
st = INF;
en = -INF;
}
}
if(st != INF) rang.push(P(st,en));
//cout << "Rang -> rang\n";
//print(rang);
if(!i) {
res = rang;
continue;
}
while(!res.empty()&&!rang.empty()) {
int x1 = res.top().first, x2 = res.top().second;
while(!rang.empty()&&rang.top().second<x1) rang.pop();
if(rang.empty()) break;
int y1 = rang.top().first, y2 = rang.top().second;
if(x2<y1) {
res.pop();
}
else {
Res.push(P(max(x1,y1),min(x2,y2)));
res.pop();
}
}
//cout << "Summation\n";
//print(Res);
res = Res;
}
if(!isPos) continue;
while(!res.empty()) {
int k1 = res.top().first, k2 = res.top().second;
ans += k2 - k1 + 1;
res.pop();
}
//cout << ans << '\n';
}
cout << ans;
}
Compilation message
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:75:13: warning: unused variable 'ry' [-Wunused-variable]
75 | int ry = y - dy * (x-rx)/dx;
| ^~
2016_ho_t4.cpp:97:13: warning: unused variable 'ry' [-Wunused-variable]
97 | int ry = y - dy * (x-rx) / dx;
| ^~
2016_ho_t4.cpp:30:12: warning: unused variable 'j' [-Wunused-variable]
30 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
