Submission #425589

#	Time	Username	Problem	Language	Result	Execution time	Memory
425589		EleCursity	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	936 ms	191852 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int readInt(){
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x;
}
int main(){
  int n = readInt();
  stack<pair<int,int> > stk;
  for(int i=1;i<=n;i++){
    int x = readInt();
    int y = readInt();
    if(stk.empty()){
      stk.push({x,y});
    }
    else{
      while(!stk.empty()){
        int xx = stk.top().first;
        int yy = stk.top().second;
        if(yy>y){
          int dx = x-xx;
          int dy = yy-y;
          if(dy<dx){
              stk.push({x,y});
          }
          break;
        }
        int dx = x-xx;
        int dy = y-yy;
        if(dy>=dx){
          stk.pop();
        }else{
          stk.push({x,y});
          break;
        }
      }
      if(stk.empty()){
        stk.push({x,y});
      }

    }
  }
  cout<<stk.size()<<endl;
  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