oj.uz

Submission #243791

# Submission time Handle Problem Language Result Execution time Memory
243791 2020-07-01T19:12:48 Z AmineWeslati Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 679 ms 262144 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 152312 KB Output is correct
2 Correct 383 ms 166648 KB Output is correct
3 Correct 369 ms 160412 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 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 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 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 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 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 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 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 3200 KB Output is correct
15 Correct 16 ms 3328 KB Output is correct
16 Correct 15 ms 3200 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 156280 KB Output is correct
2 Correct 414 ms 252536 KB Output is correct
3 Correct 406 ms 246356 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 152312 KB Output is correct
2 Correct 383 ms 166648 KB Output is correct
3 Correct 369 ms 160412 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 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 3200 KB Output is correct
18 Correct 16 ms 3328 KB Output is correct
19 Correct 15 ms 3200 KB Output is correct
20 Correct 370 ms 156280 KB Output is correct
21 Correct 414 ms 252536 KB Output is correct
22 Correct 406 ms 246356 KB Output is correct
23 Correct 679 ms 262144 KB Output is correct
24 Correct 635 ms 262144 KB Output is correct
25 Correct 621 ms 262144 KB Output is correct