oj.uz

답안 #983302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983302 2024-05-15T10:03:23 Z Malix Advertisement 2 (JOI23_ho_t2) C++14
100 / 100
 408 ms 19928 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair

ll INF=1e18+10;
ll M=1e9+7;

int main() {   
//ios::sync_with_stdio(0);
//cin.tie(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
    int n;cin>>n;
    pii a(n);
    REP(i,0,n)cin>>a[i].F>>a[i].S;
    sort(a.begin(),a.end());
    priority_queue<pi> pq;
    REP(i,0,n)pq.push({a[i].S,i});
    vi b(n,0);
    int ans=0;
    while(!pq.empty()){
        int pos=pq.top().S;
        pq.pop();
        if(b[pos]==1)continue;
        //cout<<pos<<" ";
        b[pos]=1;
        ans++;
        int g=1;
        while((pos-g>=0)&&(b[pos-g]==0)&&(a[pos].S-a[pos-g].S>=a[pos].F-a[pos-g].F)){
            //cout<<pos-g<<" ";
            b[pos-g]=1;
            g++;
        }
        g=1;
        while((pos+g<n)&&(b[pos+g]==0)&&(a[pos].S-a[pos+g].S>=a[pos+g].F-a[pos].F)){
            b[pos+g]=1;
            g++;
        }
    }
    cout<<ans;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 90 ms 5208 KB Output is correct
3 Correct 128 ms 7368 KB Output is correct
4 Correct 331 ms 18400 KB Output is correct
5 Correct 216 ms 15244 KB Output is correct
6 Correct 353 ms 19640 KB Output is correct
7 Correct 408 ms 19692 KB Output is correct
8 Correct 364 ms 19680 KB Output is correct
9 Correct 334 ms 19928 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 90 ms 5208 KB Output is correct
3 Correct 128 ms 7368 KB Output is correct
4 Correct 331 ms 18400 KB Output is correct
5 Correct 216 ms 15244 KB Output is correct
6 Correct 353 ms 19640 KB Output is correct
7 Correct 408 ms 19692 KB Output is correct
8 Correct 364 ms 19680 KB Output is correct
9 Correct 334 ms 19928 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 432 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 294 ms 13764 KB Output is correct
37 Correct 322 ms 16828 KB Output is correct
38 Correct 374 ms 19664 KB Output is correct
39 Correct 324 ms 16848 KB Output is correct
40 Correct 378 ms 19680 KB Output is correct
41 Correct 382 ms 19716 KB Output is correct
42 Correct 367 ms 19904 KB Output is correct
43 Correct 359 ms 18904 KB Output is correct
44 Correct 356 ms 19904 KB Output is correct
45 Correct 289 ms 16396 KB Output is correct