Submission #901241

#TimeUsernameProblemLanguageResultExecution timeMemory
901241duckindogOsumnjičeni (COCI21_osumnjiceni)C++14
110 / 110
224 ms32336 KiB
//from duckindog wth depressiong #include<bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int N = 2e5 + 10; int n; int lt[N], rt[N]; int f[N][19]; bool chk(pii x, pii y) { bool pass = 0; for (int i = 0; i < 2; ++i) { pass |= (x.second < y.first || x.first > y.second) ; swap(x, y); } return pass; } void init() { set<pii> duck; int j = 1; for (int i = 1; i <= n; ++i) { duck.erase({lt[i - 1], rt[i - 1]}); if (j < i) { duck.clear(); j = i; } while (j <= n) { pii now = {lt[j], rt[j]}; auto it = duck.lower_bound(now); bool pass = chk(*it, now); if (it != duck.begin()) it--; pass &= chk(*it, now); if (pass) { duck.insert(now); j += 1; } else break; } f[i][0] = j; } for (int j = 1; j <= 18; ++j) { for (int i = 1; i <= n; ++i) { f[i][j] = f[f[i][j - 1]][j - 1]; } } } int get(int l, int r) { int answer = 0; for (int i = 18; i >= 0; --i) { if (!f[l][i] || f[l][i] > r) continue; l = f[l][i]; answer += 1 << i; } return answer + 1; } int32_t main() { cin.tie(0)->sync_with_stdio(0); if (fopen("duck.inp", "r")) { freopen("duck.inp", "r", stdin); freopen("duck.out", "w", stdout); } cin >> n; for (int i = 1; i <= n; ++i) cin >> lt[i] >> rt[i]; init(); int m; cin >> m; while (m--) { int p, q; cin >> p >> q; cout << get(p, q) << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...