oj.uz

Submission #736172

# Submission time Handle Problem Language Result Execution time Memory
736172 2023-05-05T09:40:27 Z ksu2009en Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 217020 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.second == p2.second)
        return p1.first < p2.first;
    return p1.second < p2.second;
}

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[2 * 5007][2 * 5007];
vector<ll>start_here[2 * 5007];

vector<one>a;

void count_dp(one fin){
    for(int i = 0; i < a.size(); i++)
        dp[i][fin.ind] = 1e9;
    
    dp[fin.ind][fin.ind] = 0;
    
    bool ok = false;
    
    multiset<ll>st;
    
    for(int ind = a.size() - 1; ind >= 0; ind--){
        auto i = a[ind];
        
        if(i.ind == fin.ind){
            //cout << i.ind << ' ' << ind << endl;
            ok = true;
            st.insert(0);
        }
        else if(ok){
            if(st.empty()){
               // cout << "st.empty() " << i.ind << endl;
                dp[i.ind][fin.ind] = 1e9;
                st.insert(1e9);
            }
            else{
              //  cout << i.ind << endl;
              //  for(auto j: st)
              //      cout << j << ' ';
              //  cout << endl;
                dp[i.ind][fin.ind] = *st.begin();
                if(*st.begin() != (ll)(1e9))
                    dp[i.ind][fin.ind]++;
                                
                st.insert(dp[i.ind][fin.ind]);
            }
        }
        else{
           // cout << "not yet " << i.ind << endl;
            st.insert(1e9);
        }
        
        if(ind - 1 >= 0){
            for(int del = i.second; del > a[ind - 1].second; del--)
                for(auto j: start_here[del]){
                    st.erase(st.find(dp[j][fin.ind]));
                }
        }
    }
}

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(){
    srand(time(0));
    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)
        start_here[i.first].push_back(i.ind);
    
    for(auto i: a){
        count_dp(i);
    }
   
    while(q--){
        ll l, r;
        cin >> l >> r;
        //l = 1 + rand() % n, r = 1 + rand() % n;
        
        l--, r--;
        
        //auto dp2 = count_dp2(l);
        
        if(dp[l][r] == (ll)(1e9))
            cout << "impossible" << endl;
        else{
            cout << dp[l][r] << endl;
        }
    }
     
    return 0;
}
/*
 8 1
 1 2
 3 4
 1 5
 6 7
 5 10
 10 20
 15 20
 999999999 1000000000
 1 7
 
 
 */
/*
 1 2
 1 1000000000
 
 */
/*
 5 9
 2 0
 
 */
/*
 10 100
 1 3
 4 6
 2 8
 8 23
 1 4
 2 4
 6 73
 2 34
 1 9
 8 90
 
 2 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++)
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 286 ms 83132 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 62 ms 12536 KB Output is correct
4 Correct 59 ms 12592 KB Output is correct
5 Correct 85 ms 12584 KB Output is correct
6 Correct 136 ms 12584 KB Output is correct
7 Correct 160 ms 12656 KB Output is correct
8 Correct 105 ms 12660 KB Output is correct
9 Correct 113 ms 12620 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 62 ms 12536 KB Output is correct
4 Correct 59 ms 12592 KB Output is correct
5 Correct 85 ms 12584 KB Output is correct
6 Correct 136 ms 12584 KB Output is correct
7 Correct 160 ms 12656 KB Output is correct
8 Correct 105 ms 12660 KB Output is correct
9 Correct 113 ms 12620 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 53 ms 12588 KB Output is correct
13 Correct 54 ms 12584 KB Output is correct
14 Correct 65 ms 12500 KB Output is correct
15 Correct 157 ms 12504 KB Output is correct
16 Correct 160 ms 12656 KB Output is correct
17 Correct 105 ms 12656 KB Output is correct
18 Correct 103 ms 12632 KB Output is correct
19 Execution timed out 1590 ms 217020 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 62 ms 12536 KB Output is correct
4 Correct 59 ms 12592 KB Output is correct
5 Correct 85 ms 12584 KB Output is correct
6 Correct 136 ms 12584 KB Output is correct
7 Correct 160 ms 12656 KB Output is correct
8 Correct 105 ms 12660 KB Output is correct
9 Correct 113 ms 12620 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 58 ms 12584 KB Output is correct
13 Correct 59 ms 12588 KB Output is correct
14 Correct 70 ms 12592 KB Output is correct
15 Correct 126 ms 12584 KB Output is correct
16 Correct 165 ms 12752 KB Output is correct
17 Correct 117 ms 12764 KB Output is correct
18 Correct 95 ms 12544 KB Output is correct
19 Runtime error 283 ms 83196 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 281 ms 83132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 286 ms 83132 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -