This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl " "
#define endl "\n"
#define all(v) v.begin(), v.end()
#define comp(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 100100;
const int MOD = 1e9+7;
vector<pi> arr[MAXN], u, s;
vector<pll> w;
vector<int> ww;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
string str; cin >> str;
pll v = pll(0, 0); s = {v};
for(int i = 0; i < n; i++) {
if(str[i] == 'N') v.ss++;
else if(str[i] == 'S') v.ss--;
else if(str[i] == 'E') v.ff++;
else v.ff--;
s.push_back(v);
}
sort(all(s)); comp(s);
if(v == pll(0, 0) || k == 1) {
int cnt = 0;
for(auto x : s) {
if(lower_bound(all(s), pi(x.ff+1,x.ss)) != upper_bound(all(s), pi(x.ff+1,x.ss))
&& lower_bound(all(s), pi(x.ff,x.ss+1)) != upper_bound(all(s), pi(x.ff,x.ss+1))
&& lower_bound(all(s), pi(x.ff+1,x.ss+1)) != upper_bound(all(s), pi(x.ff+1,x.ss+1)) )
cnt++;
}
cout << cnt;
return 0;
}
if(v.ff == 0) {
for(auto &x : s) swap(x.ff, x.ss);
swap(v.ff, v.ss);
}
if(v.ff < 0) {
for(auto &x : s) x.ff = -x.ff;
v.ff = -v.ff;
}
for(auto x : s) w.push_back(pll(v.ff*x.ss-v.ss*x.ff, (x.ff%v.ff+v.ff)%v.ff));
sort(all(w)); comp(w);
for(auto x : s) {
int it = lower_bound(all(w), pll(v.ff*x.ss-v.ss*x.ff, (x.ff%v.ff+v.ff)%v.ff)) - w.begin();
arr[it].push_back(pi(x.ff, k-1));
}
for(int i = 0; i < w.size(); i++) {
//cout<<endl;
for(auto y : arr[i]) {
// cout<<'a'<<y.ff<<bl<<y.ss<<bl;
if(u.size() && (y.ff-u.rbegin()->ff)/v.ff <= u.rbegin()->ss) u.rbegin()->ss = (y.ff-u.rbegin()->ff)/v.ff+k-1;
else u.push_back(y);
}
swap(arr[i], u);
u.clear();
}
ll cnt = 0;
for(int i = 0; i < w.size(); i++) {
int it1 = lower_bound(all(w), pll(w[i].ff+v.ff, w[i].ss))-w.begin();
if(w[it1] != pll(w[i].ff+v.ff, w[i].ss)) continue;
int it2 = lower_bound(all(w), pll(w[i].ff-v.ss, (w[i].ss+1)%v.ff))-w.begin();
if(w[it2] != pll(w[i].ff-v.ss, (w[i].ss+1)%v.ff)) continue;
int it3 = lower_bound(all(w), pll(w[i].ff+v.ff-v.ss, (w[i].ss+1)%v.ff))-w.begin();
if(w[it3] != pll(w[i].ff+v.ff-v.ss, (w[i].ss+1)%v.ff)) continue;
ww.clear();
for(auto y : arr[i]) ww.push_back(y.ff);
for(auto y : arr[it1]) ww.push_back(y.ff);
for(auto y : arr[it2]) ww.push_back(y.ff);
for(auto y : arr[it3]) ww.push_back(y.ff);
sort(all(ww)); comp(ww);
ll p = -MOD;
for(int y : ww) {
int a = lower_bound(all(arr[i]), pi(y+1, 0)) - arr[i].begin() - 1;
int b = lower_bound(all(arr[it1]), pi(y+1, 0)) - arr[it1].begin() - 1;
int c = lower_bound(all(arr[it2]), pi(y+2, 0)) - arr[it2].begin() - 1;
int d = lower_bound(all(arr[it3]), pi(y+2, 0)) - arr[it3].begin() - 1;
if(a == -1 || b == -1 || c == -1 || d == -1) continue;
ll l = max(max(arr[i][a].ff, arr[it1][b].ff), max(arr[it2][c].ff, arr[it3][d].ff)-1);
ll r = min(min(arr[i][a].ff+v.ff*arr[i][a].ss, arr[it1][b].ff+v.ff*arr[it1][b].ss), min(arr[it2][c].ff+v.ff*arr[it2][c].ss, arr[it3][d].ff+v.ff*arr[it3][d].ss)-1);
//if(w[i] == -1) cout << l<<bl<<r<<endl;
if(p >= l) l = p + v.ff;
if(l > r) continue;
cnt += (r-l)/v.ff+1;
p = r;
}
//cout << w[i].ff<<bl<<cnt<<endl;
}
cout << cnt;
}
Compilation message (stderr)
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
2016_ho_t4.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |