oj.uz

Submission #924487

# Submission time Handle Problem Language Result Execution time Memory
924487 2024-02-09T05:34:22 Z adhityamv Advertisement 2 (JOI23_ho_t2) C++17
10 / 100
 156 ms 19652 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int INF=1000000000;
const int N=500000;
int seg[2*N];
int eminusx[N];
int n;
void build(){
    for(int i=0;i<n;i++){
        seg[i+n]=i;
    }
    for(int i=n-1;i>=0;i--){
        seg[i]=max(mp(eminusx[seg[2*i]],seg[2*i]),mp(eminusx[seg[2*i+1]],seg[2*i+1])).second;
    }
}
int query(int l,int r){
    l+=n;
    r+=n;
    pii ans=mp(-INF,-INF);
    while(l<r){
        if(l&1){
            ans=max(ans,mp(eminusx[seg[l]],seg[l]));
            l++;
        }
        if(r&1){
            r--;
            ans=max(ans,mp(eminusx[seg[r]],seg[r]));
        }
        l>>=1;
        r>>=1;
    }
    return ans.second;
}
void solve(){
    cin >>n;
    int x[n];
    int e[n];
    for(int i=0;i<n;i++){
        cin >> x[i] >> e[i];
    }
    vector<pii> tosort;
    for(int i=0;i<n;i++) tosort.push_back(mp(e[i]+x[i],i));
    sort(tosort.begin(),tosort.end());
    for(int i=0;i<n;i++) eminusx[i]=e[tosort[i].second]-x[tosort[i].second];
    build();
    int cnt=0;
    int ind=-1;
    while(ind!=n-1){
        ind=query(ind+1,n);
        cnt++;
    }
    cout << cnt << "\n";
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin >> t;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 42 ms 8064 KB Output is correct
3 Correct 58 ms 9668 KB Output is correct
4 Correct 120 ms 18476 KB Output is correct
5 Correct 65 ms 14512 KB Output is correct
6 Correct 156 ms 19388 KB Output is correct
7 Correct 145 ms 19560 KB Output is correct
8 Correct 131 ms 19560 KB Output is correct
9 Correct 95 ms 19652 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2608 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Incorrect 1 ms 2648 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2608 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Incorrect 1 ms 2648 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 42 ms 8064 KB Output is correct
3 Correct 58 ms 9668 KB Output is correct
4 Correct 120 ms 18476 KB Output is correct
5 Correct 65 ms 14512 KB Output is correct
6 Correct 156 ms 19388 KB Output is correct
7 Correct 145 ms 19560 KB Output is correct
8 Correct 131 ms 19560 KB Output is correct
9 Correct 95 ms 19652 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2508 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2608 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Incorrect 1 ms 2648 KB Output isn't correct
26 Halted 0 ms 0 KB -