oj.uz

Submission #602680

# Submission time Handle Problem Language Result Execution time Memory
602680 2022-07-23T10:05:50 Z almothana05 Event Hopping (BOI22_events) C++14
20 / 100
 1158 ms 43972 KB 
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
vector<vector<int> >num;
vector<pair<int , int > >cmp;
vector<int>pow2;
int ind[200000] , platz[200000];
int lift[300000][20], seg[20][800000];
unordered_map<int , int>trans;
int sucher(int id , int l , int r , int gewl , int gewr , int ver){
    if(gewl > r || l > gewr){
        return mod;
    }
    if(gewl <= l && r <= gewr){
        return seg[ver][id];
    }
    int m = (l + r)/2;
    return min(sucher(id * 2 , l , m , gewl , gewr , ver) , sucher(id * 2 + 1 , m + 1 , r , gewl ,gewr , ver));
}
int main(){
    int menge , numm , nummer , que , len;
    cin >> menge >> que;
    for(int i = 1 ; i < 1000000 ; i*= 2){
        pow2.push_back(i);
    }
    for(len = 1 ; len < 100000 ; len *= 2);
    for(int i = 0 ; i < menge ; i++){
        platz[i + 1]  = -1;
        cin >> numm >> nummer;
        num.push_back({nummer , numm , i + 1});
        cmp.push_back({numm , 0});
        cmp.push_back({nummer , 1});
    }
    int pl = 0;// does matter sort begin?
    sort(cmp.begin() , cmp.end());
    sort(num.begin() , num.end());
    for(int i = cmp.size() - 1 ; i >= 0; i--){
        if(trans[cmp[i].first] == 0 && cmp[i].second == 1){
            // cout << cmp[i].first << ' ';
            pl++;
        }//////////////////////////////////////////////////////////////
        trans[cmp[i].first] = pl;
    }
    pl++;
    // cout << "\n";
    for(int i = 0 ; i < num.size() ; i++){
        // cout << num[i][0] << ' ' << num[i][1] << "\n";
        num[i][0] = pl - trans[num[i][0]];
        num[i][1] = pl - trans[num[i][1]];
        ind[num[i][2]] = i;
        if(platz[num[i][0]] == -1){
            platz[num[i][0]] = i;
        }
        lift[i][0] = num[i][1];
        // cout << num[i][0]<< ' ' << num[i][1]<< "\n\n";
    }
    for(int i = 1 ; i < 20 ; i++){
        // cout << i << ' ';
        for(int j = 0 ; j < 100000; j++){
            seg[i - 1][j + len] = lift[j][i - 1];
        }
        for(int j = len - 1 ; j > 0 ; j--){
            seg[i - 1][j] = min(seg[i - 1][j * 2] , seg[i - 1][j * 2 + 1]);
        }
        for(int j = 0 ; j < num.size(); j++){
            lift[j][i] = sucher(1 , 1 , len , platz[lift[j][i - 1]] + 1 , j + 1 , i - 1);
        }
        // cout << i  << " \n";
    }
    // for(int i = 0 ; i < menge ; i++){
    //     for(int j = 0 ; j < 20 ; j++){
    //         cout << lift[i][j] << ' ';
    //     }
    //     cout << "\n";
    // }
    int erg;
    while(que--){
        erg = 0;
        cin >> numm >> nummer;
        if(numm == nummer){
            cout << 0 << "\n";
            continue;
        }
        numm = ind[numm];
        nummer = ind[nummer];
        // cout << numm <<' ' << nummer  << "\n";
        if(numm > nummer){
            cout << "impossible\n";
            continue;
        }
        int be = nummer , en = nummer;
        for(int i = 19 ; i >= 0 ; i--){
            int comp = sucher(1 , 1, len , be + 1 , en + 1 , i ) ;
                // cout << comp << " ";
            if( comp > num[numm][0]){
                // cout << i << ' ' ;
                erg += pow2[i];
                be = platz[comp];
            }
        }
        // cout << "\n";
        // cout <<  nummer << " \n";
        be = platz[sucher(1 , 1, len , be + 1 , en + 1 , 0 )];
        // cout << numm << ' ' << be << ' ' << en << "\n";
        if(numm >= be){
            cout << erg + 1 << "\n";
        }
        else{
            cout << "impossible\n";
        }
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0 ; i < num.size() ; i++){
      |                     ~~^~~~~~~~~~~~
events.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int j = 0 ; j < num.size(); j++){
      |                         ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17620 KB Output is correct
2 Correct 1106 ms 38776 KB Output is correct
3 Correct 1122 ms 38604 KB Output is correct
4 Correct 1101 ms 38604 KB Output is correct
5 Correct 1158 ms 38732 KB Output is correct
6 Correct 1118 ms 38992 KB Output is correct
7 Correct 1070 ms 39096 KB Output is correct
8 Correct 806 ms 43904 KB Output is correct
9 Correct 840 ms 43852 KB Output is correct
10 Correct 1112 ms 39048 KB Output is correct
11 Incorrect 936 ms 39944 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17620 KB Output is correct
2 Correct 12 ms 17592 KB Output is correct
3 Correct 16 ms 17848 KB Output is correct
4 Correct 16 ms 17876 KB Output is correct
5 Correct 15 ms 17804 KB Output is correct
6 Correct 21 ms 17920 KB Output is correct
7 Correct 16 ms 17876 KB Output is correct
8 Correct 21 ms 17876 KB Output is correct
9 Incorrect 17 ms 17748 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17620 KB Output is correct
2 Correct 12 ms 17592 KB Output is correct
3 Correct 16 ms 17848 KB Output is correct
4 Correct 16 ms 17876 KB Output is correct
5 Correct 15 ms 17804 KB Output is correct
6 Correct 21 ms 17920 KB Output is correct
7 Correct 16 ms 17876 KB Output is correct
8 Correct 21 ms 17876 KB Output is correct
9 Incorrect 17 ms 17748 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17620 KB Output is correct
2 Correct 12 ms 17592 KB Output is correct
3 Correct 16 ms 17848 KB Output is correct
4 Correct 16 ms 17876 KB Output is correct
5 Correct 15 ms 17804 KB Output is correct
6 Correct 21 ms 17920 KB Output is correct
7 Correct 16 ms 17876 KB Output is correct
8 Correct 21 ms 17876 KB Output is correct
9 Incorrect 17 ms 17748 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 38492 KB Output is correct
2 Correct 1114 ms 38556 KB Output is correct
3 Correct 1102 ms 38692 KB Output is correct
4 Correct 835 ms 43972 KB Output is correct
5 Correct 1074 ms 39076 KB Output is correct
6 Correct 982 ms 43548 KB Output is correct
7 Correct 988 ms 43732 KB Output is correct
8 Correct 1102 ms 43704 KB Output is correct
9 Correct 417 ms 42840 KB Output is correct
10 Correct 1024 ms 43200 KB Output is correct
11 Correct 863 ms 43120 KB Output is correct
12 Correct 1004 ms 43252 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17620 KB Output is correct
2 Correct 1106 ms 38776 KB Output is correct
3 Correct 1122 ms 38604 KB Output is correct
4 Correct 1101 ms 38604 KB Output is correct
5 Correct 1158 ms 38732 KB Output is correct
6 Correct 1118 ms 38992 KB Output is correct
7 Correct 1070 ms 39096 KB Output is correct
8 Correct 806 ms 43904 KB Output is correct
9 Correct 840 ms 43852 KB Output is correct
10 Correct 1112 ms 39048 KB Output is correct
11 Incorrect 936 ms 39944 KB Output isn't correct
12 Halted 0 ms 0 KB -