Submission #874189

#	Time	Username	Problem	Language	Result	Execution time	Memory
874189		garam1732	영역 (JOI16_ho_t4)	C++14	100 / 100	47 ms	8400 KiB

2016_ho_t4

#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; sort(all(s)); comp(s);
        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;
    }
 	
    sort(all(s)); comp(s);
    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();
    }
//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;
 
        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; 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 (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:93: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]
   93 |     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++;
      |                   ~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 62 / 62