Submission #138937

#	Time	Username	Problem	Language	Result	Execution time	Memory
138937		thebes	Lightning Rod (NOI18_lightningrod)	C++14	80 / 100	2052 ms	77716 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

int n, i, x, y, f, a, b, sz=-1, X[10000005], Y[10000005];

int main(){
    scan(n);
    for(i=1;i<=n;i++){
        scan(x); scan(y); f=0;
        while(sz!=-1){
            if(x-X[sz]<=Y[sz]-y) break;
            else if(y-Y[sz]>=x-X[sz]) sz--;
            else{f=1; break;}
        }
        if(sz==-1||f){
            ++sz;
            X[sz] = x;
            Y[sz] = y;
        }
    }
    printf("%d\n",sz+1);
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 0 / 20