Submission #895498

#	Time	Username	Problem	Language	Result	Execution time	Memory
895498		1bin	Event Hopping (BOI22_events)	C++14	100 / 100	99 ms	20132 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 18;
int n, q, p[b][18], s[b], e[b], l, r;
pair<int, int> seg[b * 2];
vector<int> tmp;

void upd(int ix, pair<int, int> v){
    ix += b;
    while(ix){
        seg[ix] = min(seg[ix], v);
        ix /= 2;
    }
    return;
}

int qry(int l, int r){
    l += b; r += b;
    pair<int, int> ret = {2e9, -1};
    while(l <= r){
        if(l & 1) ret = min(ret, seg[l++]);
        if(!(r & 1)) ret = min(ret, seg[r--]);
        l /= 2; r /= 2;
    }
    return ret.second;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> s[i] >> e[i];
        tmp.emplace_back(s[i]);
        tmp.emplace_back(e[i]);
    }    
    sort(all(tmp));
    tmp.erase(unique(all(tmp)), tmp.end());

    memset(seg, 0x3f, sizeof(seg));
    for(int i = 1; i <= n; i++) {
        s[i] = lower_bound(all(tmp), s[i]) - tmp.begin();
        e[i] = lower_bound(all(tmp), e[i]) - tmp.begin(); 
        upd(e[i], {s[i], i});
    }
    for(int i = 1; i <= n; i++) p[i][0] = qry(s[i], e[i]);
    for(int j = 1; j < 17; j++)
        for(int i = 1; i <= n; i++) p[i][j] = p[p[i][j - 1]][j - 1];
    
    while(q--){
        cin >> l >> r;
        if(l == r) cout << "0\n";
        else if(e[r] < e[l]) cout << "impossible\n";
        else if(e[l] >= s[r]) cout << "1\n";
        else{
            int ans = 0;
            for(int i = 16; i >= 0; i--)
                if(e[l] < s[p[r][i]]) r = p[r][i], ans += 1 << i;
            if(s[p[r][0]] <= e[l]) cout << ans + 2 << '\n';
            else cout << "impossible\n";
        }
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:44:34: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   44 |     memset(seg, 0x3f, sizeof(seg));
      |                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30