Submission #1046213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046213		shjeong	Comparing Plants (IOI20_plants)	C++17	100 / 100	1812 ms	191432 KiB

plants

#include <cstdio>
#include <cassert>
#include <vector>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
ll n;
struct lazyseg{ //min query
    vector<ll> tree, lazy;
    lazyseg(): tree(808080), lazy(808080){}
    void prop(ll node, ll s, ll e){
        if(!lazy[node])return;
        tree[node] += lazy[node];
        if(s^e)lazy[node<<1] += lazy[node], lazy[node<<1|1] += lazy[node]; lazy[node]=0;
    }
    void init(ll node, ll s, ll e, vector<int> &v){
        if(s==e){
            tree[node] = v[s];
        }
        else{
            ll mid = s+e>>1;
            init(node<<1,s,mid,v); init(node<<1|1,mid+1,e,v);
            tree[node] = min(tree[node<<1], tree[node<<1|1]);
        }
    }
    void upd(ll node, ll s, ll e, ll l, ll r, ll x){
        prop(node,s,e);
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            lazy[node] = x;
            prop(node,s,e); return;
        }
        ll mid = s+e>>1;
        upd(node<<1,s,mid,l,r,x); upd(node<<1|1,mid+1,e,l,r,x);
        tree[node] = min(tree[node<<1], tree[node<<1|1]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        prop(node,s,e);
        if(e<l or r<s)return 1e18;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1; return min(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
    ll find_pos(ll idx){    //idx 이상
        if(query(1,0,n-1,idx,n-1) > 0)return -1;
        ll l = idx-1, r = n;
        while(l+1 < r){
            ll mid = l+r>>1;
            if(query(1,0,n-1,idx,mid) == 0)r = mid; else l = mid;
        }
        return r;
    }
} seg;
struct segtree{
    vector<pair<ll,ll>> tree;
    segtree(): tree(1616161){}
    void upd(ll node, ll s, ll e, ll i, ll d){
        if(e<i or i<s)return;
        if(s==e)tree[node] = {d+1,s};
        else{
            ll mid = s+e>>1;
            upd(node<<1,s,mid,i,d); upd(node<<1|1,mid+1,e,i,d);
            tree[node] = max(tree[node<<1],tree[node<<1|1]);
        }
    }
    pair<ll,ll> query(ll node, ll s, ll e, ll l, ll r){
        if(e<l or r<s)return {-1,0};
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1; return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
} maxseg;
ll L[404040][22], R[404040][22];
vector<ll> v;
bool chk(ll l, ll r){
    l = (l+n)%n;
    r = (r+n)%n;
    if(l<=r)return seg.query(1,0,n-1,l,r) > 0;
    return min(seg.query(1,0,n-1,l,n-1), seg.query(1,0,n-1,0,r)) > 0;
}
void subs(ll l, ll r){
    l = (l+n)%n;
    r = (r+n)%n;
    if(l<=r)seg.upd(1,0,n-1,l,r,-1);
    else{
        seg.upd(1,0,n-1,l,n-1,-1);
        seg.upd(1,0,n-1,0,r,-1);
    }
}
ll K;
void init(int k, std::vector<int> r) {
    n = r.size(); k--;
    K=k;
    seg.init(1,0,n-1,r);
    vector<ll> cand;
    for(int i = 0 ; i < n ; i++)if(r[i] == 0){
        if(chk(i-k, i-1))cand.push_back(i);
    }
    v.resize(n*2);
    for(int t = 0 ; cand.size() ; t++){
        vector<ll> nxt;
        for(auto i : cand){
            v[i] = v[n+i] = n-t, subs(i-k, i-1);
            seg.upd(1,0,n-1,i,i,1e9);
        }
        for(auto i : cand){
            ll l = (i-k+n)%n, r = (i-1+n)%n;
            ll p = -1;
            if(l<=r){
                p = seg.find_pos(l);
                if((l <= p and p <= r) and chk(p-k,p-1))nxt.push_back(p);
            }
            else{
                p = seg.find_pos(l);
                if(p==-1)p = seg.find_pos(0);
                if(((l <= p and p <= n) or (0 <= p and p <= r)) and chk(p-k,p-1))nxt.push_back(p);
            }
            l = (i+1)%n, r = (i+k)%n;
            p = -1;
            if(l<=r){
                p = seg.find_pos(l);
                if((l <= p and p <= r) and chk(p-k,p-1))nxt.push_back(p);
            }
            else{
                p = seg.find_pos(l);
                if(p==-1)p = seg.find_pos(0);
                if(((l <= p and p <= n) or (0 <= p and p <= r)) and chk(p-k,p-1))nxt.push_back(p);
            }
        }
        cand.clear(); sort(all(nxt)); comp(nxt); for(auto i : nxt)cand.push_back(i);
    }
    vector<pair<ll,ll>> e;
    for(int i = 0 ; i < n ; i++)e.push_back({v[i],i});
    sort(all(e));
    memset(L,-1,sizeof(L));
    memset(R,-1,sizeof(R));
    for(auto [d,x] : e){
        if(x-k >= 0){
            auto [_,t] = maxseg.query(1,0,n*2-1, x-k, x-1);
            if(_ > 0)L[x][0] = t;
        }
        if(x+k < n*2){
            auto [_,t] = maxseg.query(1,0,n*2-1, x+1, x+k);
            if(_ > 0)R[x][0] = t;
        }
        
        if(x+n-k >= 0){
            auto [_,t] = maxseg.query(1,0,n*2-1, x+n-k, x+n-1);
            if(_ > 0)L[n+x][0] = t;
        }
        if(x+n+k < n*2){
            auto [_,t] = maxseg.query(1,0,n*2-1, x+n+1, x+n+k);
            if(_ > 0)R[n+x][0] = t;
        }
        maxseg.upd(1,0,n*2-1,x,d);
        maxseg.upd(1,0,n*2-1,x+n,d);
    }
    for(int j = 1 ; j <= 20 ; j++){
        for(int i = 0 ; i < n*2 ; i++){
            if(L[i][j-1] < 0)L[i][j] = -1;
            else if(L[L[i][j-1]][j-1] < 0)L[i][j] = -1;
            else L[i][j] = L[L[i][j-1]][j-1];
            
            if(R[i][j-1] < 0)R[i][j] = -1;
            else if(R[R[i][j-1]][j-1] < 0)R[i][j] = -1;
            else R[i][j] = R[R[i][j-1]][j-1];
        }
    }
}

int compare_plants(int x, int y) {
    if(x < y){
        ll nx = x;  //x < y
        for(int i = 20 ; i >= 0 ; i--){
            if(R[nx][i] < 0 or R[nx][i] + K >= y)continue;
            nx = R[nx][i];
        }
        if(nx + K < y)nx = R[nx][0];
        if(nx>=0 and nx + K >= y and v[nx] > v[y])return 1;
        nx = n+x;
        for(int i = 20 ; i >= 0 ; i--){
            if(L[nx][i] < 0 or L[nx][i] - K <= y)continue;
            nx = L[nx][i];
        }
        if(nx - K > y)nx = L[nx][0];
        if(nx>=0 and nx - K <= y and v[nx] > v[y])return 1;
        swap(x,y);  //x > y
        nx = x;
        for(int i = 20 ; i >= 0 ; i--){
            if(L[nx][i] < 0 or L[nx][i] - K <= y)continue;
            nx = L[nx][i];
        }
        if(nx - K > y)nx = L[nx][0];
        if(nx>=0 and nx - K <= y and v[nx] > v[y])return -1;
        nx = x;
        for(int i = 20 ; i >= 0 ; i--){
            if(R[nx][i] < 0 or R[nx][i] + K >= n+y)continue;
            nx = R[nx][i];
        }
        if(nx + K < n+y)nx = R[nx][0];
        if(nx>=0 and nx + K >= n+y and v[nx] > v[n+y])return -1;
    }
    else{
        ll nx = x; //x > y
        for(int i = 20 ; i >= 0 ; i--){
            if(L[nx][i] < 0 or L[nx][i] - K <= y)continue;
            nx = L[nx][i];
        }
        if(nx - K > y)nx = L[nx][0];
        if(nx>=0 and nx - K <= y and v[nx] > v[y])return 1;
        nx = x;
        for(int i = 20 ; i >= 0 ; i--){
            if(R[nx][i] < 0 or R[nx][i] + K >= n+y)continue;
            nx = R[nx][i];
        }
        if(nx + K < n+y)nx = R[nx][0];
        if(nx>=0 and nx + K >= n+y and v[nx] > v[n+y])return 1;
        swap(x,y);  //x < y
        nx = x;
        for(int i = 20 ; i >= 0 ; i--){
            if(R[nx][i] < 0 or R[nx][i] + K >= y)continue;
            nx = R[nx][i];
        }
        if(nx + K < y)nx = R[nx][0];
        if(nx>=0 and nx + K >= y and v[nx] > v[y])return -1;
        nx = n+x;
        for(int i = 20 ; i >= 0 ; i--){
            if(L[nx][i] < 0 or L[nx][i] - K <= y)continue;
            nx = L[nx][i];
        }
        if(nx - K > y)nx = L[nx][0];
        if(nx>=0 and nx - K <= y and v[nx] > v[y])return -1;
    }
    return 0;
}

Compilation message (stderr)

plants.cpp: In member function 'void lazyseg::prop(ll, ll, ll)':
plants.cpp:17:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |         if(s^e)lazy[node<<1] += lazy[node], lazy[node<<1|1] += lazy[node]; lazy[node]=0;
      |         ^~
plants.cpp:17:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   17 |         if(s^e)lazy[node<<1] += lazy[node], lazy[node<<1|1] += lazy[node]; lazy[node]=0;
      |                                                                            ^~~~
plants.cpp: In member function 'void lazyseg::init(ll, ll, ll, std::vector<int>&)':
plants.cpp:24:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |             ll mid = s+e>>1;
      |                      ~^~
plants.cpp: In member function 'void lazyseg::upd(ll, ll, ll, ll, ll, ll)':
plants.cpp:36:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         ll mid = s+e>>1;
      |                  ~^~
plants.cpp: In member function 'll lazyseg::query(ll, ll, ll, ll, ll)':
plants.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         ll mid = s+e>>1; return min(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
      |                  ~^~
plants.cpp: In member function 'll lazyseg::find_pos(ll)':
plants.cpp:50:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |             ll mid = l+r>>1;
      |                      ~^~
plants.cpp: In member function 'void segtree::upd(ll, ll, ll, ll, ll)':
plants.cpp:63:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |             ll mid = s+e>>1;
      |                      ~^~
plants.cpp: In member function 'std::pair<long long int, long long int> segtree::query(ll, ll, ll, ll, ll)':
plants.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         ll mid = s+e>>1; return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
      |                  ~^~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25