| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 874180 |
2023-11-16T12:02:59 Z |
garam1732 |
None (JOI16_ho_t4) |
C++14 |
|
1 ms |
2652 KB |
#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);
}
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++) {
sort(all(arr[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();
}
//cout<<endl;
// for(int i = 0; i < w.size(); i++) {
// cout<<w[i].ff<<endl;
// for(pi x : arr[i]) cout<<x.ff<<bl<<x.ss<<bl;
// cout<<endl;
// }
// arr[0] = {pi(0, 2)};
// arr[1] = {pi(1, 1), pi(2, 1)};
// arr[2] = {pi(1, 2), pi(2, 1)};
// arr[3] = {pi(2, 2), pi(3, 1)};
// arr[4] = {pi(4, 1)};
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;
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; int a = 0, b = 0, c = 0, d = 0;
for(int y : ww) {
while(a+1 < arr[i].size() && arr[i][a+1].ff <= y) a++;
while(b+1 < arr[it1].size() && arr[it1][b+1].ff <= y) b++;
while(c+1 < arr[it2].size() && arr[it2][c+1].ff <= y+1) c++;
while(d+1 < arr[it3].size() && arr[it3][d+1].ff <= y+1) d++;
if(arr[i][a].ff > y || arr[it1][b].ff > y || arr[it2][c].ff > y+1 || arr[it3][d].ff > y+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
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:67: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]
67 | for(int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
2016_ho_t4.cpp:94: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]
94 | for(int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
2016_ho_t4.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while(a+1 < arr[i].size() && arr[i][a+1].ff <= y) a++;
| ~~~~^~~~~~~~~~~~~~~
2016_ho_t4.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | while(b+1 < arr[it1].size() && arr[it1][b+1].ff <= y) b++;
| ~~~~^~~~~~~~~~~~~~~~~
2016_ho_t4.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | while(c+1 < arr[it2].size() && arr[it2][c+1].ff <= y+1) c++;
| ~~~~^~~~~~~~~~~~~~~~~
2016_ho_t4.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | while(d+1 < arr[it3].size() && arr[it3][d+1].ff <= y+1) d++;
| ~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
