oj.uz

Submission #602627

# Submission time Handle Problem Language Result Execution time Memory
602627 2022-07-23T09:37:01 Z almothana05 Event Hopping (BOI22_events) C++14
20 / 100
 1185 ms 47056 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][500000];
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";
    }
    // cout << "ja\n";
    for(int i = 1 ; i < 20 ; 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);
        }
    }
    // 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 12 ms 17544 KB Output is correct
2 Correct 1081 ms 41736 KB Output is correct
3 Correct 1095 ms 41652 KB Output is correct
4 Correct 1090 ms 41448 KB Output is correct
5 Correct 1067 ms 41840 KB Output is correct
6 Correct 1053 ms 42100 KB Output is correct
7 Correct 1061 ms 42328 KB Output is correct
8 Correct 822 ms 47056 KB Output is correct
9 Correct 794 ms 46836 KB Output is correct
10 Correct 971 ms 42000 KB Output is correct
11 Incorrect 938 ms 43148 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 17580 KB Output is correct
3 Correct 16 ms 17804 KB Output is correct
4 Correct 16 ms 17740 KB Output is correct
5 Correct 15 ms 17724 KB Output is correct
6 Correct 16 ms 17768 KB Output is correct
7 Correct 16 ms 17876 KB Output is correct
8 Correct 15 ms 17876 KB Output is correct
9 Incorrect 15 ms 17716 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 17580 KB Output is correct
3 Correct 16 ms 17804 KB Output is correct
4 Correct 16 ms 17740 KB Output is correct
5 Correct 15 ms 17724 KB Output is correct
6 Correct 16 ms 17768 KB Output is correct
7 Correct 16 ms 17876 KB Output is correct
8 Correct 15 ms 17876 KB Output is correct
9 Incorrect 15 ms 17716 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 17580 KB Output is correct
3 Correct 16 ms 17804 KB Output is correct
4 Correct 16 ms 17740 KB Output is correct
5 Correct 15 ms 17724 KB Output is correct
6 Correct 16 ms 17768 KB Output is correct
7 Correct 16 ms 17876 KB Output is correct
8 Correct 15 ms 17876 KB Output is correct
9 Incorrect 15 ms 17716 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 1048 ms 41752 KB Output is correct
2 Correct 1100 ms 41712 KB Output is correct
3 Correct 1085 ms 41340 KB Output is correct
4 Correct 807 ms 46792 KB Output is correct
5 Correct 963 ms 41852 KB Output is correct
6 Correct 1010 ms 46676 KB Output is correct
7 Correct 971 ms 46536 KB Output is correct
8 Correct 1135 ms 46876 KB Output is correct
9 Correct 508 ms 44628 KB Output is correct
10 Correct 1121 ms 46244 KB Output is correct
11 Correct 971 ms 45976 KB Output is correct
12 Correct 1185 ms 46124 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17544 KB Output is correct
2 Correct 1081 ms 41736 KB Output is correct
3 Correct 1095 ms 41652 KB Output is correct
4 Correct 1090 ms 41448 KB Output is correct
5 Correct 1067 ms 41840 KB Output is correct
6 Correct 1053 ms 42100 KB Output is correct
7 Correct 1061 ms 42328 KB Output is correct
8 Correct 822 ms 47056 KB Output is correct
9 Correct 794 ms 46836 KB Output is correct
10 Correct 971 ms 42000 KB Output is correct
11 Incorrect 938 ms 43148 KB Output isn't correct
12 Halted 0 ms 0 KB -