oj.uz

Submission #416266

# Submission time Handle Problem Language Result Execution time Memory
416266 2021-06-02T09:09:09 Z strawberry2005 Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 776 ms 175988 KB 
#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define nl '\n'
const int mod = 1e9+7;
#define deb(x) cout<<#x<<": "<<x<<endl

int iceil(int a, int b) {
  return (a + b - 1) / b;
}
int mod_fun(int a, int mod){
  while(a < 0) a += mod;
  return a % mod;
}

int readInt()
{
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}

signed main(){

    #ifdef strawberryshaker2005
        freopen("input.txt", "r", stdin);
    #endif

    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);

    int n=readInt();
    stack<pair<int,int>> s;
    for(int i=0;i<n;i++){
        int x=readInt(),y=readInt();

        while(!s.empty()&&abs(x-s.top().F)<=y-s.top().S){
            s.pop();
        }
        if(s.empty()||abs(x-s.top().F)>s.top().S-y) s.push({x,y});
        
    }
    printf("%d",s.size());


    return(0);
    
}

Compilation message

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:54:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
   54 |     printf("%d",s.size());
      |             ~^  ~~~~~~~~
      |              |        |
      |              int      std::stack<std::pair<int, int> >::size_type {aka long unsigned int}
      |             %ld

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 79820 KB Output is correct
2 Correct 416 ms 79388 KB Output is correct
3 Correct 394 ms 77260 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 14 ms 3844 KB Output is correct
15 Correct 16 ms 3592 KB Output is correct
16 Correct 16 ms 3636 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 51224 KB Output is correct
2 Correct 437 ms 147708 KB Output is correct
3 Correct 423 ms 144140 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 79820 KB Output is correct
2 Correct 416 ms 79388 KB Output is correct
3 Correct 394 ms 77260 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 14 ms 3844 KB Output is correct
18 Correct 16 ms 3592 KB Output is correct
19 Correct 16 ms 3636 KB Output is correct
20 Correct 383 ms 51224 KB Output is correct
21 Correct 437 ms 147708 KB Output is correct
22 Correct 423 ms 144140 KB Output is correct
23 Correct 776 ms 175988 KB Output is correct
24 Correct 763 ms 156984 KB Output is correct
25 Correct 765 ms 140252 KB Output is correct