oj.uz

Submission #1000458

# Submission time Handle Problem Language Result Execution time Memory
1000458 2024-06-17T14:21:50 Z anango Event Hopping (BOI22_events) C++17
20 / 100
 407 ms 69416 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 && end<=start) {
            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++) {
      |                   ~^~~~~~~~~~~~~~
events.cpp:98:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   98 |         if (x==y || startstart<=endstart && end<=start) {
      |                     ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 283 ms 42920 KB Output is correct
3 Correct 289 ms 41640 KB Output is correct
4 Correct 292 ms 43132 KB Output is correct
5 Correct 305 ms 44952 KB Output is correct
6 Correct 277 ms 46804 KB Output is correct
7 Correct 317 ms 47524 KB Output is correct
8 Correct 324 ms 68772 KB Output is correct
9 Correct 325 ms 69416 KB Output is correct
10 Correct 299 ms 42148 KB Output is correct
11 Incorrect 323 ms 52644 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 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Incorrect 2 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 344 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Incorrect 2 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 344 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Incorrect 2 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 289 ms 41684 KB Output is correct
2 Correct 299 ms 42648 KB Output is correct
3 Correct 302 ms 42396 KB Output is correct
4 Correct 330 ms 69276 KB Output is correct
5 Correct 300 ms 43112 KB Output is correct
6 Correct 384 ms 68772 KB Output is correct
7 Correct 392 ms 68772 KB Output is correct
8 Correct 382 ms 68520 KB Output is correct
9 Correct 317 ms 67888 KB Output is correct
10 Correct 380 ms 68512 KB Output is correct
11 Correct 407 ms 67900 KB Output is correct
12 Correct 381 ms 68760 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 283 ms 42920 KB Output is correct
3 Correct 289 ms 41640 KB Output is correct
4 Correct 292 ms 43132 KB Output is correct
5 Correct 305 ms 44952 KB Output is correct
6 Correct 277 ms 46804 KB Output is correct
7 Correct 317 ms 47524 KB Output is correct
8 Correct 324 ms 68772 KB Output is correct
9 Correct 325 ms 69416 KB Output is correct
10 Correct 299 ms 42148 KB Output is correct
11 Incorrect 323 ms 52644 KB Output isn't correct
12 Halted 0 ms 0 KB -