Submission #933234

#TimeUsernameProblemLanguageResultExecution timeMemory
933234WhisperOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
62 ms41812 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define FOR(i, a, b) for ( int i = a ; i <= b ; i++ ) #define FORD(i, a, b) for (int i = b; i >= a; i --) #define REP(i, n) for (int i = 0; i < n; ++i) #define REPD(i, n) for (int i = n - 1; i >= 0; --i) #define pii pair<int , int> #define Lg(x) 31 - __builtin_clz(x) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int MAX = 2e5 + 5; constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void setupIO(){ #define name "Whisper" //Phu Trong from Nguyen Tat Thanh High School for gifted student srand(time(NULL)); cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); cout << fixed << setprecision(10); } template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } int nArr, numQuery; pair<int, int> a[MAX]; int nxt[MAX][22]; void Whisper(){ cin >> nArr; for (int i = 1; i <= nArr; ++i) cin >> a[i].first >> a[i].second; set<pair<int, int>> s; auto Add = [&](pair<int, int> x){ auto iter = s.lower_bound(x); if (iter != s.end()){ pair<int, int> left = *(iter); if (left.first <= x.second) return false; } if (iter != s.begin()){ pair<int, int> right = *prev(iter); if (right.second >= x.first) return false; } s.insert(x); return true; }; FOR(i, 0, nArr + 2) FOR(k, 0, 21) nxt[i][k] = nArr + 1; int l = 1; for (int i = 1; i <= nArr; ++i){ while (l <= nArr && Add(a[l])) l++; nxt[i][0] = l; s.erase(a[i]); } for (int i = 1; i <= nArr; ++i){ for (int k = 1; k <= 21; ++k){ nxt[i][k] = nxt[nxt[i][k - 1]][k - 1]; } } cin >> numQuery; for (int i = 1; i <= numQuery; ++i){ int l, r; cin >> l >> r; int ans = 0; for (int i = 21; i >= 0; --i){ if (nxt[l][i] <= r) ans += MASK(i), l = nxt[l][i]; } cout << ans + 1 << '\n'; } } signed main(){ setupIO(); int Test = 1; // cin >> Test; for ( int i = 1 ; i <= Test ; i++ ){ Whisper(); if (i < Test) cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...