Submission #1264808

#TimeUsernameProblemLanguageResultExecution timeMemory
1264808SoMotThanhXuanOsumnjičeni (COCI21_osumnjiceni)C++20
110 / 110
438 ms27624 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i) #define mp make_pair #define all(v) v.begin(), v.end() #define uni(v) v.erase(unique(all(v)), v.end()) #define Bit(x, i) ((x >> (i)) & 1) #define Mask(i) (1 << (i)) #define Cnt(x) __builtin_popcount(x) #define Cntll(x) __builtin_popcountll(x) #define Ctz(x) __builtin_ctz(x) #define Ctzll(x) __builtin_ctzll(x) #define Clz(x) __builtin_clz(x) #define Clzll(x) __builtin_clzll(x) inline bool maximize(int &u, int v){ return v > u ? u = v, true : false; } inline bool minimize(int &u, int v){ return v < u ? u = v, true : false; } inline bool maximizell(long long &u, long long v){ return v > u ? u = v, true : false; } inline bool minimizell(long long &u, long long v){ return v < u ? u = v, true : false; } const int mod = 1e9 + 7; inline int fastPow(int a, int n){ if(n == 0) return 1; int t = fastPow(a, n >> 1); t = 1ll * t * t % mod; if(n & 1) t = 1ll * t * a % mod; return t; } inline void add(int &u, int v){ u += v; if(u >= mod) u -= mod; } inline void sub(int &u, int v){ u -= v; if(u < 0) u += mod; } const int maxN = 2e5 + 5; const int inf = 1e9; const long long infll = 1e18; int n, l[maxN], r[maxN], q; vector<int> comp; int it[maxN << 3], lz[maxN << 3]; void build(int id, int l, int r){ if(l == r){ it[id] = inf; lz[id] = inf; return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); it[id] = inf; lz[id] = inf; } void push(int id){ if(lz[id] == inf) return; FOR(v, id << 1, id << 1 | 1){ minimize(lz[v], lz[id]); minimize(it[v], lz[id]); } lz[id] = inf; return; } void update(int id, int l, int r, int u, int v, int w){ if(l > v || r < u) return; if(l >= u && r <= v){ minimize(it[id], w); minimize(lz[id], w); return; } push(id); int mid = l + r >> 1; update(id << 1, l, mid, u, v, w); update(id << 1 | 1, mid + 1, r, u, v, w); it[id] = min(it[id << 1], it[id << 1 | 1]); } int get(int id, int l, int r, int u, int v){ if(l >= u && r <= v) return it[id]; int mid = l + r >> 1; push(id); if(v <= mid) return get(id << 1, l, mid, u, v); if(u > mid) return get(id << 1 | 1, mid + 1, r, u, v); return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } int nxt[maxN][18], lg[maxN]; void process(){ cin >> n; FOR(i, 1, n){ cin >> l[i] >> r[i]; comp.emplace_back(l[i]); comp.emplace_back(r[i]); } sort(all(comp)); uni(comp); int sz = comp.size(); build(1, 1, sz); FOR(i, 1, n){ l[i] = lower_bound(all(comp), l[i]) - comp.begin() + 1; r[i] = lower_bound(all(comp), r[i]) - comp.begin() + 1; } nxt[n][0] = n; update(1, 1, sz, l[n], r[n], n); REP(i, n - 1, 1){ int minId = get(1, 1, sz, l[i], r[i]); nxt[i][0] = min(minId - 1, nxt[i + 1][0]); update(1, 1, sz, l[i], r[i], i); } FOR(i, 2, n)lg[i] = lg[i >> 1] + 1; FOR(j, 0, lg[n])nxt[n + 1][j] = 0; FOR(j, 1, lg[n]){ FOR(i, 1, n) if(nxt[i][j - 1] == 0)nxt[i][j] = 0; else nxt[i][j] = nxt[nxt[i][j - 1] + 1][j - 1]; } // FOR(j, 0, lg[n]){ // FOR(i, 1, n)cout << nxt[i][j] << ' '; // cout << '\n'; // } cin >> q; // FOR(i, 1, n)cout << nxt[i][0] << ' ';cout << '\n'; while(q--){ int l, r; cin >> l >> r; int p = l; int answer = 0; REP(j, 17, 0){ if(nxt[p][j] <= r && nxt[p][j] >= p){ // cout << p << ' ' << Mask(j) << ' ' << nxt[p][j] << '\n'; p = nxt[p][j] + 1; answer += Mask(j); } } if(p <= r)++answer; cout << answer << '\n'; } } #define LOVE "lineup" int main(){ if(fopen(LOVE".inp", "r")){ freopen(LOVE".inp", "r", stdin); freopen(LOVE".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while(t--) process(); // cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(LOVE".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(LOVE".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...