Submission #650743

#	Time	Username	Problem	Language	Result	Execution time	Memory
650743		fatemetmhr	Triangles (CEOI18_tri)	C++17	100 / 100	417 ms	1428 KiB

tri

//  ~Be name khoda~  //

#include<bits/stdc++.h>
#include "trilib.h"

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int sq    =  200;
const ll  inf   =  2e18;

int nxt[maxn5], pre[maxn5];
int st, sqnxt[maxn5];

inline int get(int d){
    int v = st;
    while(d >= sq){
        d -= sq;
        v = sqnxt[v];
    }
    while(d--)
        v = nxt[v];
    return v;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int n = get_n();
    nxt[1] = 2; nxt[2] = 3; nxt[3] = 1;
    pre[1] = 3; pre[2] = 1; pre[3] = 2;
    int need = sq;
    sqnxt[1] = 1; sqnxt[2] = 2; sqnxt[3] = 3;
    while(need--){
        sqnxt[1] = nxt[sqnxt[1]];
        sqnxt[2] = nxt[sqnxt[2]];
        sqnxt[3] = nxt[sqnxt[3]];
    }
    if(n == 3){
        give_answer(3);
        return 0;
    }
    st = 1;
    int sz = 3;
    for(int i = 4; i <= n; i++){
        int out = -1;
        bool hullorder = is_clockwise(st, nxt[st], nxt[nxt[st]]);
        bool ans = is_clockwise(st, nxt[st], i);
        ans ^= hullorder;
        if(ans){
            out = st;
        }
        else{
            int lo = 0, hi = sz - 2;
            while(hi - lo > 1){
                int mid = (lo + hi) >> 1;
                if(hullorder ^ is_clockwise(st, get(mid + 1), i))
                    hi = mid;
                else
                    lo = mid;
            }
            if(hi == sz - 2 && is_clockwise(st, pre[st], nxt[st]) != is_clockwise(st, pre[st], i)){
                lo = hi;
                //cout << "oh spc case " << endl;
                if(is_clockwise(pre[st], st, nxt[st]) != is_clockwise(pre[st], st, i))
                    out = pre[st];
            }
            else{
                int lolo = get(lo + 1);
                if(is_clockwise(lolo, nxt[lolo], nxt[nxt[lolo]]) != is_clockwise(lolo, nxt[lolo], i))
                    out = lolo;
            }
        }
        if(out == -1)
            continue;
        for(out = nxt[out]; ; out = nxt[out])
            if(is_clockwise(out, nxt[out], nxt[nxt[out]]) == is_clockwise(out, nxt[out], i))
                break;
        int r = out;
        for(out = pre[out]; ; out = pre[out]){
            if(is_clockwise(out, pre[out], pre[pre[out]]) == is_clockwise(out, pre[out], i))
                break;
            sz--;
        }
        sz++;
        int l = out;
        nxt[l] = i;
        pre[r] = i;
        nxt[i] = r;
        pre[i] = l;
        st = i;
        int need = sq;
        int have = i;
        while(need--)
            have = nxt[have];
        sqnxt[i] = have;
        need = sq + 4;
        have = i;
        while(need--){
            have = pre[have];
            sqnxt[have] = pre[sqnxt[nxt[have]]];
        }
    }
    int num = 1;
    for(int i = nxt[st]; i != st; i = nxt[i]) num++;
    give_answer(num);
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25