oj.uz

Submission #736153

# Submission time Handle Problem Language Result Execution time Memory
736153 2023-05-05T09:08:28 Z ksu2009en Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 13456 KB 
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

struct one{
    ll first, second, ind;
};

bool cmp(one p1, one p2){
    if(p1.first == p2.first)
        return p1.second < p2.second;
    return p1.first < p2.first;
}

void compress(vector<one> &a){
    vector<ll>b;
    for(auto i: a){
        b.push_back(i.first);
        b.push_back(i.second);
    }
    
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    
    ll step = 1;
    map<ll, ll> mp;
    for(auto i: b)
        mp[i] = step++;
    
    for(auto &i: a){
        i.first = mp[i.first];
        i.second = mp[i.second];
    }
}

ll dp[5007][5007];
vector<ll>end_here[5007];

vector<one>a;

void count_dp(one start){
    for(int i = 0; i < a.size(); i++)
        dp[start.ind][i] = 1e9;
    
    dp[start.ind][start.ind] = 0;
    
    bool ok = false;
    
    multiset<ll>st;
    
    for(int ind = 0; ind < a.size(); ind++){
        auto i = a[ind];
        
        if(i.ind == start.ind){
            ok = true;
            st.insert(0);
        }
        else if(ok){
            if(st.empty()){
                dp[start.ind][i.ind] = 1e9;
                st.insert(1e9);
            }
            else{
                dp[start.ind][i.ind] = *st.begin();
                if(*st.begin() != (ll)(1e9))
                    dp[start.ind][i.ind]++;
                
                st.insert(dp[start.ind][i.ind]);
            }
        }
        else
            st.insert(1e9);
        
        if(ind + 1 < a.size()){
            for(int del = i.first; del < a[ind + 1].first; del++)
                for(auto j: end_here[del]){
                    st.erase(st.find(dp[start.ind][j]));
                }
        }
    }
}

vector<ll>count_dp2(ll start){
    vector<ll>dp2(a.size(), 1e9);
    
    dp2[start] = 0;
    
    for(auto i: a){
        for(auto j: a){
            if(i.first <= j.second && j.second <= i.second){
                dp2[i.ind] = min(dp2[i.ind], dp2[j.ind] + 1);
            }
        }
    }
    
    return dp2;
}

int main(){
    ll n, q;
    cin >> n >> q;
    
    a.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
        a[i].ind = i;
    }
    
    compress(a);
    sort(a.begin(), a.end(), cmp);
    
    for(auto i: a)
        end_here[i.second].push_back(i.ind);
   
    while(q--){
        ll l, r;
        cin >> l >> r;
        
        l--, r--;
        
        auto dp2 = count_dp2(l);
        
        if(dp2[r] == (ll)(1e9))
            cout << "impossible" << endl;
        else
            cout << dp2[r] << endl;
    }
     
    return 0;
}
/*
 8 1
 1 2
 3 4
 1 5
 6 7
 5 10
 10 20
 15 20
 999999999 1000000000
 3 3
 */

Compilation message

events.cpp: In function 'void count_dp(one)':
events.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<one>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
events.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<one>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int ind = 0; ind < a.size(); ind++){
      |                      ~~~~^~~~~~~~~~
events.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<one>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(ind + 1 < a.size()){
      |            ~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1584 ms 13448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 75 ms 468 KB Output is correct
4 Correct 75 ms 548 KB Output is correct
5 Correct 78 ms 544 KB Output is correct
6 Correct 186 ms 468 KB Output is correct
7 Correct 320 ms 596 KB Output is correct
8 Correct 226 ms 596 KB Output is correct
9 Correct 331 ms 440 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 75 ms 468 KB Output is correct
4 Correct 75 ms 548 KB Output is correct
5 Correct 78 ms 544 KB Output is correct
6 Correct 186 ms 468 KB Output is correct
7 Correct 320 ms 596 KB Output is correct
8 Correct 226 ms 596 KB Output is correct
9 Correct 331 ms 440 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 88 ms 468 KB Output is correct
13 Correct 93 ms 468 KB Output is correct
14 Correct 96 ms 428 KB Output is correct
15 Correct 190 ms 468 KB Output is correct
16 Correct 310 ms 596 KB Output is correct
17 Correct 199 ms 596 KB Output is correct
18 Correct 325 ms 468 KB Output is correct
19 Execution timed out 1563 ms 1284 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 75 ms 468 KB Output is correct
4 Correct 75 ms 548 KB Output is correct
5 Correct 78 ms 544 KB Output is correct
6 Correct 186 ms 468 KB Output is correct
7 Correct 320 ms 596 KB Output is correct
8 Correct 226 ms 596 KB Output is correct
9 Correct 331 ms 440 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 82 ms 468 KB Output is correct
13 Correct 77 ms 468 KB Output is correct
14 Correct 95 ms 468 KB Output is correct
15 Correct 187 ms 436 KB Output is correct
16 Correct 328 ms 596 KB Output is correct
17 Correct 203 ms 596 KB Output is correct
18 Correct 334 ms 468 KB Output is correct
19 Execution timed out 1572 ms 13208 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 13456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1584 ms 13448 KB Time limit exceeded
3 Halted 0 ms 0 KB -