oj.uz

Submission #243792

# Submission time Handle Problem Language Result Execution time Memory
243792 2020-07-01T19:12:57 Z AmineWeslati Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 617 ms 201168 KB 
//Never stop trying
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//s.order_of_key(), *s.find_by_order()

using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0}; //right left down up

inline int readInt(){
   int x=0; bool s=1;
   char c=getchar_unlocked();
   if(c<'0'||c>'9'){
      if(c=='-') s=0;
      c=getchar_unlocked();
   }
   while(c>='0' && c<='9'){
      x=(x<<3)+(x<<1)+c-'0';
      c=getchar_unlocked();
   }
   return s? x: -x;
}

const int MX=1e7;
int mx[MX],mx2[MX];

int32_t main(){
   boost;
   int N; N=readInt();

   for(int i=0; i<N; i++){
      int x=readInt(),y=readInt();
      mx[i]=x+y;
      mx2[i]=y-x;
   }

   for(int i=0; i<N; i++){
      if(i) mx[i]=max(mx[i-1],mx[i]);
   }
   for(int i=N-1; i>=0; i--){
      if(i<N-1) mx2[i]=max(mx2[i+1],mx2[i]);
   }
   int res=0;
   for(int i=0; i<N; i++){
      if((!i && mx2[i]>mx2[i+1])||(i==N-1 && mx[i]>mx[i-1])||(mx[i]>mx[i-1] && mx2[i]>mx2[i+1])) res++;
   }
   cout << res << endl;

   return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 170616 KB Output is correct
2 Correct 373 ms 169464 KB Output is correct
3 Correct 374 ms 163068 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 17 ms 4224 KB Output is correct
15 Correct 16 ms 4224 KB Output is correct
16 Correct 16 ms 4112 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 170204 KB Output is correct
2 Correct 382 ms 159096 KB Output is correct
3 Correct 383 ms 155256 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 170616 KB Output is correct
2 Correct 373 ms 169464 KB Output is correct
3 Correct 374 ms 163068 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 17 ms 4224 KB Output is correct
18 Correct 16 ms 4224 KB Output is correct
19 Correct 16 ms 4112 KB Output is correct
20 Correct 388 ms 170204 KB Output is correct
21 Correct 382 ms 159096 KB Output is correct
22 Correct 383 ms 155256 KB Output is correct
23 Correct 617 ms 201168 KB Output is correct
24 Correct 550 ms 181744 KB Output is correct
25 Correct 508 ms 162656 KB Output is correct