oj.uz

Submission #1000461

# Submission time Handle Problem Language Result Execution time Memory
1000461 2024-06-17T14:25:06 Z anango Event Hopping (BOI22_events) C++17
20 / 100
 409 ms 69996 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 || (startstart<=endstart && endstart<=start)) {
            cout << (x==y?0: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 320 ms 42164 KB Output is correct
3 Correct 304 ms 43036 KB Output is correct
4 Correct 329 ms 41892 KB Output is correct
5 Correct 301 ms 44400 KB Output is correct
6 Correct 315 ms 47516 KB Output is correct
7 Correct 306 ms 47576 KB Output is correct
8 Incorrect 335 ms 69024 KB Output isn't correct
9 Halted 0 ms 0 KB -

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 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 344 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 344 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 283 ms 41860 KB Output is correct
2 Correct 297 ms 42404 KB Output is correct
3 Correct 300 ms 42920 KB Output is correct
4 Correct 342 ms 69996 KB Output is correct
5 Correct 305 ms 43484 KB Output is correct
6 Correct 405 ms 68520 KB Output is correct
7 Correct 391 ms 69584 KB Output is correct
8 Correct 381 ms 68576 KB Output is correct
9 Correct 314 ms 68508 KB Output is correct
10 Correct 381 ms 68308 KB Output is correct
11 Correct 409 ms 67748 KB Output is correct
12 Correct 361 ms 68176 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 320 ms 42164 KB Output is correct
3 Correct 304 ms 43036 KB Output is correct
4 Correct 329 ms 41892 KB Output is correct
5 Correct 301 ms 44400 KB Output is correct
6 Correct 315 ms 47516 KB Output is correct
7 Correct 306 ms 47576 KB Output is correct
8 Incorrect 335 ms 69024 KB Output isn't correct
9 Halted 0 ms 0 KB -