oj.uz

Submission #1000462

# Submission time Handle Problem Language Result Execution time Memory
1000462 2024-06-17T14:27:13 Z anango Event Hopping (BOI22_events) C++17
30 / 100
 468 ms 69820 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 startstart = events[x].first;
        int start = events[x].second;
        int endstart = events[y].first;
        int end = events[y].second;
        if (x==y) {
            cout << (x==y?0:1) << 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++) {
      |                   ~^~~~~~~~~~~~~~
events.cpp:94:13: warning: unused variable 'startstart' [-Wunused-variable]
   94 |         int startstart = events[x].first;
      |             ^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 284 ms 41700 KB Output is correct
3 Correct 277 ms 42632 KB Output is correct
4 Correct 301 ms 42472 KB Output is correct
5 Correct 272 ms 44804 KB Output is correct
6 Correct 286 ms 47772 KB Output is correct
7 Correct 317 ms 49064 KB Output is correct
8 Correct 314 ms 68772 KB Output is correct
9 Correct 375 ms 69820 KB Output is correct
10 Correct 306 ms 42148 KB Output is correct
11 Correct 319 ms 53404 KB Output is correct
12 Correct 221 ms 42524 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 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 41892 KB Output is correct
2 Correct 286 ms 41684 KB Output is correct
3 Correct 301 ms 41892 KB Output is correct
4 Correct 321 ms 68880 KB Output is correct
5 Correct 303 ms 42412 KB Output is correct
6 Correct 371 ms 69592 KB Output is correct
7 Correct 468 ms 68524 KB Output is correct
8 Correct 381 ms 69272 KB Output is correct
9 Correct 324 ms 68404 KB Output is correct
10 Correct 373 ms 68172 KB Output is correct
11 Correct 390 ms 67844 KB Output is correct
12 Correct 382 ms 68764 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 284 ms 41700 KB Output is correct
3 Correct 277 ms 42632 KB Output is correct
4 Correct 301 ms 42472 KB Output is correct
5 Correct 272 ms 44804 KB Output is correct
6 Correct 286 ms 47772 KB Output is correct
7 Correct 317 ms 49064 KB Output is correct
8 Correct 314 ms 68772 KB Output is correct
9 Correct 375 ms 69820 KB Output is correct
10 Correct 306 ms 42148 KB Output is correct
11 Correct 319 ms 53404 KB Output is correct
12 Correct 221 ms 42524 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 860 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 -