제출 #1190438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190438		dzuizz	Lightning Rod (NOI18_lightningrod)	C++20	100 / 100	230 ms	76200 KiB

Main

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e8;
inline int read(){
#define num (ch&15)
  char ch; int res;
  while(!isdigit(ch=getchar_unlocked()));
  for(res=num;isdigit(ch=getchar_unlocked());res=(res<<3)+(res<<1)+num);
#undef num
  return res;
}
int n,l[N],r[N],s=-1;
int main(){
  n=read();
  for(int i=0,x,y;i<n;++i){
    x=read(),y=read();
    while(s>=0&&x-y<=l[s]-r[s]) --s;
    if(s<0||x+y>l[s]+r[s]) l[++s]=x,r[s]=y;
  }
  printf("%d\n",++s);
  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: 20 / 20