oj.uz

Submission #1000453

# Submission time Handle Problem Language Result Execution time Memory
1000453 2024-06-17T14:16:13 Z anango Event Hopping (BOI22_events) C++17
30 / 100
 494 ms 72604 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
    //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:40: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]
   40 |     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 349 ms 42360 KB Output is correct
3 Correct 350 ms 42392 KB Output is correct
4 Correct 364 ms 46244 KB Output is correct
5 Correct 375 ms 48680 KB Output is correct
6 Correct 340 ms 49828 KB Output is correct
7 Correct 369 ms 52276 KB Output is correct
8 Correct 406 ms 72572 KB Output is correct
9 Correct 393 ms 72600 KB Output is correct
10 Correct 362 ms 46504 KB Output is correct
11 Correct 404 ms 55728 KB Output is correct
12 Correct 292 ms 44784 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 2 ms 604 KB Output is correct
4 Correct 2 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 2 ms 604 KB Output is correct
4 Correct 2 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 2 ms 604 KB Output is correct
4 Correct 2 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 344 ms 41988 KB Output is correct
2 Correct 351 ms 42396 KB Output is correct
3 Correct 360 ms 44712 KB Output is correct
4 Correct 377 ms 72604 KB Output is correct
5 Correct 372 ms 45936 KB Output is correct
6 Correct 453 ms 71588 KB Output is correct
7 Correct 494 ms 71588 KB Output is correct
8 Correct 482 ms 71712 KB Output is correct
9 Correct 363 ms 70212 KB Output is correct
10 Correct 432 ms 71332 KB Output is correct
11 Correct 473 ms 71324 KB Output is correct
12 Correct 415 ms 72096 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 349 ms 42360 KB Output is correct
3 Correct 350 ms 42392 KB Output is correct
4 Correct 364 ms 46244 KB Output is correct
5 Correct 375 ms 48680 KB Output is correct
6 Correct 340 ms 49828 KB Output is correct
7 Correct 369 ms 52276 KB Output is correct
8 Correct 406 ms 72572 KB Output is correct
9 Correct 393 ms 72600 KB Output is correct
10 Correct 362 ms 46504 KB Output is correct
11 Correct 404 ms 55728 KB Output is correct
12 Correct 292 ms 44784 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Incorrect 1 ms 860 KB Output isn't correct
18 Halted 0 ms 0 KB -