| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 967204 |
2024-04-21T13:46:44 Z |
TB_ |
Curtains (NOI23_curtains) |
C++17 |
|
1 ms |
452 KB |
#include <bits/stdc++.h>
using namespace std;
// #undef _GLIBCXX_DEBUG // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
// #pragma GCC target("movbe") // byte swap
// #pragma GCC target("aes,pclmul,rdrnd") // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define INF ((ll)(1e9+7))
#define fo(i, n) for(ll i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << (x) << endl;
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;
struct UnionFind{
int n;
vl p, siz;
UnionFind(int n) : n(n){
p.assign(n, 1);
siz.assign(n, 1);
fo(i, n) p[i] = i;
}
bool same(int a, int b){
return find(a) == find(b);
}
int find(int x){
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
if(siz[b] > siz[a]) swap(a, b);
p[b] = a;
siz[a] += siz[b];
}
};
bool customSort(tuple<ll, ll, ll> &a, tuple<ll, ll, ll> &b){
if(get<0>(a) == get<0>(b)) return get<1>(a) > get<1>(b);
return get<0>(a) < get<0>(b);
}
int main() {
// cout << fixed << setprecision(20);
// auto start = std::chrono::steady_clock::now(); // since(start).count()
cin.tie(0)->sync_with_stdio(0);
int n, m, q;
cin >> n >> m >> q;
UnionFind uf(n+1);
int a, b;
vpl sections;
fo(i, m){
cin >> a >> b;
sections.pb({a, -b});
}
sort(rall(sections));
vector<tuple<ll, ll, ll>> que;
fo(i, q){
cin >> a >> b;
que.pb({a, b, i});
}
sort(all(que), customSort);
vl ans(q, 0);
stack<pl> prev; // from, to
fo(i, m){
tie(a, b) = sections[i];
b = -b;
while(!prev.empty() && prev.top().F<=b+1){
uf.unite(prev.top().S, b);
prev.pop();
}
prev.push({a, b});
while(que.size() && get<0>(que[que.size()-1])>a) que.pop_back();
while(que.size() && (i == m-1 || sections[i].F != sections[i+1].F || -sections[i+1].S>get<1>(que[que.size()-1])) &&
get<0>(que[que.size()-1])==a){
if(b<=get<1>(que[que.size()-1]))ans[get<2>(que[que.size()-1])] = uf.same(get<1>(que[que.size()-1]), b);
que.pop_back();
}
}
fo(i, q) cout << (ans[i]?"YES":"NO") << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
