Submission #138936

#	Time	Username	Problem	Language	Result	Execution time	Memory
138936		thebes	Lightning Rod (NOI18_lightningrod)	C++14	80 / 100	2045 ms	122892 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;
pair<int,int> st[10000005];

int main(){
    scan(n);
    for(i=1;i<=n;i++){
        scan(x); scan(y); f=0;
        while(sz!=-1){
            a = st[sz].first, b = st[sz].second;
            if(x-a<=b-y) break;
            else if(y-b>=x-a) sz--;
            else{f=1; break;}
        }
        if(sz==-1||f) st[++sz]={x,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