Submission #1279540

#TimeUsernameProblemLanguageResultExecution timeMemory
1279540hssaan_arifCurtains (NOI23_curtains)C++20
0 / 100
1 ms568 KiB
// #include <me> #include <bits/stdc++.h> using namespace std; #define endl "\n" #define pb push_back #define int long long #define fi first #define se second const int N = 5e5 + 5, M = 1e9 + 7, LG = 20; int n , m , q , l , r , Fen[N]; void add(int i , int x){ while(i <= n){ Fen[i] += x; i += (i & (-i)); } } int prep(int i){ int ans = 0; while(i > 0){ ans += Fen[i]; i -= (i & (-i)); } return ans; } void solve(){ cin >> n >> m >> q; bool dp[n+1] = {} , vi[n+1] = {}; vector<pair<int,int>> s; for (int i = 1 ; i <= m ; i++){ cin >> l >> r; if (l == 1){ dp[r] = 1; } if (vi[r] == 0){ s.pb({r , l}); vi[r] = 1; } } sort(s.begin() , s.end()); l = 0; for (int j = 1 ; j <= n ; j++){ while(l < s.size() && s[l].fi < j){ l++; } if (l < s.size() && 1 <= s[l].se && s[l].fi == j){ int k = s[l].se - 1; int tp = prep(j) - prep(k-1); if (tp){ dp[j] = 1; add(j , 1); }else{ dp[j] = 0; add(j , 0); } } } while(q--){ cin >> l >> r; // cout << dp[l][r] << endl; if (dp[r]){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ts = 1; // cin >> ts; while(ts--){ solve(); } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...