oj.uz

Submission #1000460

# Submission time Handle Problem Language Result Execution time Memory
1000460 2024-06-17T14:24:05 Z anango Event Hopping (BOI22_events) C++17
20 / 100
 408 ms 70052 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;
        }
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 288 ms 42456 KB Output is correct
3 Correct 307 ms 42648 KB Output is correct
4 Correct 302 ms 41636 KB Output is correct
5 Correct 304 ms 44268 KB Output is correct
6 Correct 305 ms 48036 KB Output is correct
7 Correct 303 ms 47524 KB Output is correct
8 Correct 339 ms 70052 KB Output is correct
9 Correct 333 ms 69112 KB Output is correct
10 Correct 301 ms 43252 KB Output is correct
11 Incorrect 359 ms 53204 KB Output isn't correct
12 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 293 ms 42744 KB Output is correct
2 Correct 310 ms 41636 KB Output is correct
3 Correct 308 ms 42264 KB Output is correct
4 Correct 350 ms 69800 KB Output is correct
5 Correct 315 ms 43432 KB Output is correct
6 Correct 406 ms 69844 KB Output is correct
7 Correct 384 ms 69276 KB Output is correct
8 Correct 395 ms 68484 KB Output is correct
9 Correct 331 ms 67748 KB Output is correct
10 Correct 381 ms 69020 KB Output is correct
11 Correct 408 ms 67752 KB Output is correct
12 Correct 384 ms 68708 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 288 ms 42456 KB Output is correct
3 Correct 307 ms 42648 KB Output is correct
4 Correct 302 ms 41636 KB Output is correct
5 Correct 304 ms 44268 KB Output is correct
6 Correct 305 ms 48036 KB Output is correct
7 Correct 303 ms 47524 KB Output is correct
8 Correct 339 ms 70052 KB Output is correct
9 Correct 333 ms 69112 KB Output is correct
10 Correct 301 ms 43252 KB Output is correct
11 Incorrect 359 ms 53204 KB Output isn't correct
12 Halted 0 ms 0 KB -