oj.uz

Submission #1000454

# Submission time Handle Problem Language Result Execution time Memory
1000454 2024-06-17T14:16:36 Z anango Event Hopping (BOI22_events) C++17
30 / 100
 419 ms 69028 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;


signed main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        //freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        //freopen("output.txt", "w", stdout);
    #endif
    /*#ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif*/ //fast IO
    ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    //for each time t, compute latest[t] = latest time you can get to with at most 1 switch starting at t
    //then binary lifting
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> events;
    vector<vector<int>> sweep;
    vector<int> coords;
    map<int,int> revcoords;
    for (int i=0; i<n; i++) {
        int st,en;
        cin >> st >> en;
        events.push_back({st,en});
        coords.push_back(st);
        coords.push_back(en);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()),coords.end());
    
    int k = coords.size();
    for (int i=0; i<k; i++) {
        revcoords[coords[i]] = i;
    }
    
    for (int i=0; i<events.size(); i++) {
        int st,en;
        st=events[i].first;
        en=events[i].second;
        sweep.push_back({revcoords[st],-1,i});
        sweep.push_back({revcoords[en],1,i});
        events[i] = {revcoords[st],revcoords[en]};
    }
    sort(sweep.begin(), sweep.end());
    set<int> indices;
    multiset<int> endings;
    vector<int> latest(k,-1);
    
    for (auto ev:sweep) {
        int a,b,ind;
        a=ev[0];
        b=ev[1];
        ind=ev[2];
        if (b==-1) {
            indices.insert(ind);
            endings.insert(events[ind].second);
        }
        else {
            indices.erase(ind);
            endings.erase(endings.find(events[ind].second));
        }
        if (endings.size()) {
            latest[a] = *endings.rbegin();
        }
        else {
            latest[a] = a;
        }
    }
    int maxlift=20;
    vector<vector<int>> lift(k,vector<int>(maxlift+1,-1));
    for (int i=0; i<k; i++) {
        lift[i][0] = latest[i];
        //cout << i <<" " << latest[i] << endl;
    }
    for (int p=0; p<maxlift; p++) {
        for (int i=0; i<k; i++) {
            lift[i][p+1] = lift[lift[i][p]][p];
            //cout << i <<" " << p+1 <<" " << lift[i][p+1] << endl;
        }
    }

    for (int i=0; i<q; i++) {
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        int answer = 0;
        int start = events[x].second;
        int endstart = events[y].first;
        int end = events[y].second;
        if (x==y) {
            cout << 0 << endl;
            continue;
        }
        if (endstart <= start && start<=end) {
            cout << 1 << endl;
            continue;
        }
        int cur = start;
        for (int p=maxlift; p>=0; p--) {
            int ncur = lift[cur][p];
            //cout << p <<" " << cur <<" " << ncur << endl;
            if (ncur<endstart) {
                cur=ncur;
                answer+=1LL<<p;
            }
        }
        cur=lift[cur][0];
        //cout << "DOING " << start << " " << end << " " << cur << endl;

        if (!(endstart<=cur && cur<=end)) {
            cout << "impossible" << endl;
        }
        else {
            cout << answer+2 << endl;
        }
    }

}

Compilation message

events.cpp: In function 'int main()':
events.cpp:42:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0; i<events.size(); i++) {
      |                   ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 291 ms 42292 KB Output is correct
3 Correct 294 ms 42136 KB Output is correct
4 Correct 281 ms 42580 KB Output is correct
5 Correct 298 ms 44480 KB Output is correct
6 Correct 293 ms 47012 KB Output is correct
7 Correct 305 ms 48036 KB Output is correct
8 Correct 318 ms 69028 KB Output is correct
9 Correct 330 ms 68772 KB Output is correct
10 Correct 288 ms 41896 KB Output is correct
11 Correct 332 ms 52896 KB Output is correct
12 Correct 205 ms 42376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Incorrect 1 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Incorrect 1 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Incorrect 1 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 41536 KB Output is correct
2 Correct 333 ms 41700 KB Output is correct
3 Correct 303 ms 41636 KB Output is correct
4 Correct 309 ms 68848 KB Output is correct
5 Correct 306 ms 42404 KB Output is correct
6 Correct 371 ms 68564 KB Output is correct
7 Correct 393 ms 68516 KB Output is correct
8 Correct 412 ms 68772 KB Output is correct
9 Correct 311 ms 68504 KB Output is correct
10 Correct 360 ms 68816 KB Output is correct
11 Correct 419 ms 68000 KB Output is correct
12 Correct 371 ms 68056 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 291 ms 42292 KB Output is correct
3 Correct 294 ms 42136 KB Output is correct
4 Correct 281 ms 42580 KB Output is correct
5 Correct 298 ms 44480 KB Output is correct
6 Correct 293 ms 47012 KB Output is correct
7 Correct 305 ms 48036 KB Output is correct
8 Correct 318 ms 69028 KB Output is correct
9 Correct 330 ms 68772 KB Output is correct
10 Correct 288 ms 41896 KB Output is correct
11 Correct 332 ms 52896 KB Output is correct
12 Correct 205 ms 42376 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Incorrect 1 ms 860 KB Output isn't correct
18 Halted 0 ms 0 KB -