oj.uz

Submission #1094650

# Submission time Handle Problem Language Result Execution time Memory
1094650 2024-09-30T08:15:35 Z razivo Event Hopping (BOI22_events) C++14
30 / 100
 335 ms 24536 KB 
#include <iostream>
#include <climits>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int main()
{
    int N,Q;
    cin>>N>>Q;
    vector<pair<int,int>> events;
    vector<pair<pair<int,int>,int>> u;
    for (int i = 0; i < N; ++i) {
        int x,y;
        cin>>x>>y;
        events.emplace_back(x,y);
        u.emplace_back(make_pair(x,0),i);
        u.emplace_back(make_pair(y,1),i);
    }
    sort(u.begin(),u.end());
    vector<vector<int>> lift(N);
    set<pair<int,int>> s;
    for (int i = 0; i < 2*N; ++i) {
        auto [a,j] = u[i];
        if(events[j].first==a.first) {
            s.insert({-events[j].second,j});
        }else {
            s.erase({-events[j].second,j});
            auto t = s.lower_bound({-INT_MAX,0});
            if(t!=s.end()) {
                lift[j].push_back(t->second);
            }else lift[j].push_back(j);
        }
    }
    int pos = 0;
    for(int i = 1; i<N; i*=2) {
        for (int j = 0; j < N; ++j) {
            if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
                lift[j].push_back(lift[lift[j][pos]][pos]);
            }
        }
        pos++;
    }
    for (int i = 0; i < Q; ++i) {
        int s,e;
        cin>>s>>e; s--; e--;
        int ans = 0;
        bool t = true;
        while(s!=e) {
            if(events[e].first<=events[s].second&&events[s].second<=events[e].second) {
                ans++;
                break;
            }
            if(events[lift[s][0]].second>events[e].second) {
                cout<<"impossible"<<endl;
                s=e;
                t= false;
                continue;
            }
            int j = 1;
            int u = 1;
            while(j<lift[s].size()&&events[lift[s][j]].second<events[e].second){ j++; u*=2;}
            ans+=u;
            j--;
            if(s==lift[s][j]) {
                cout<<"impossible"<<endl;
                s=e;
                t= false;
                continue;
            }
            s= lift[s][j];
        }
        if(t) cout<<ans<<endl;
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [a,j] = u[i];
      |              ^
events.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
      |                ~~~^~~~~~~~~~~~~~~
events.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(pos<lift[j].size()&&pos<lift[lift[j][pos]].size()) {
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             while(j<lift[s].size()&&events[lift[s][j]].second<events[e].second){ j++; u*=2;}
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 276 ms 22900 KB Output is correct
3 Correct 300 ms 22732 KB Output is correct
4 Correct 335 ms 22856 KB Output is correct
5 Correct 327 ms 22956 KB Output is correct
6 Correct 305 ms 24276 KB Output is correct
7 Correct 329 ms 24220 KB Output is correct
8 Correct 292 ms 24532 KB Output is correct
9 Correct 248 ms 24536 KB Output is correct
10 Correct 295 ms 24536 KB Output is correct
11 Correct 297 ms 24528 KB Output is correct
12 Correct 213 ms 23444 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 1 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Incorrect 1 ms 604 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 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Incorrect 1 ms 604 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 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Incorrect 1 ms 604 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 23768 KB Output is correct
2 Correct 295 ms 23768 KB Output is correct
3 Correct 317 ms 23944 KB Output is correct
4 Correct 240 ms 24276 KB Output is correct
5 Correct 269 ms 24252 KB Output is correct
6 Correct 277 ms 24020 KB Output is correct
7 Correct 283 ms 24012 KB Output is correct
8 Correct 292 ms 24140 KB Output is correct
9 Correct 123 ms 22232 KB Output is correct
10 Correct 288 ms 22740 KB Output is correct
11 Correct 271 ms 22484 KB Output is correct
12 Correct 322 ms 22736 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 276 ms 22900 KB Output is correct
3 Correct 300 ms 22732 KB Output is correct
4 Correct 335 ms 22856 KB Output is correct
5 Correct 327 ms 22956 KB Output is correct
6 Correct 305 ms 24276 KB Output is correct
7 Correct 329 ms 24220 KB Output is correct
8 Correct 292 ms 24532 KB Output is correct
9 Correct 248 ms 24536 KB Output is correct
10 Correct 295 ms 24536 KB Output is correct
11 Correct 297 ms 24528 KB Output is correct
12 Correct 213 ms 23444 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Incorrect 1 ms 604 KB Output isn't correct
18 Halted 0 ms 0 KB -