Submission #222200

#TimeUsernameProblemLanguageResultExecution timeMemory
222200ryanseeTrampoline (info1cup20_trampoline)C++14
0 / 100
808 ms81708 KiB
#include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define pb push_back #define eb emplace_back #define ins insert #define f first #define s second #define cbr cerr << "hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ll(x.size()) #define all(x) (x).begin(), (x).end() #define lbd(x,y) (lower_bound(all(x),y)-x.begin()) #define ubd(x,y) (upper_bound(all(x),y)-x.begin()) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); } typedef long long ll; typedef long double ld; #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i) #define DEC(i,s,e) for(ll i=s;i>=ll(e);--i) typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi; #define LLINF ((long long)1e18) #define INF int(1e9+1e6) #define MAXN (400006) ll r,c,n,q; pi A[MAXN],pos[MAXN]; vector<ll> d,dc; vector<pi> row[MAXN],col[MAXN]; bitset<MAXN>ans; int p[MAXN]; int find(int x) { return (p[x]==x) ? x : p[x]=find(p[x]); } void merge(int x,int y){return void(p[find(x)]=find(y)); } bool same(int a,int b){return find(a)==find(b);} bitset<MAXN>vis; vector<spi>Q; int main(){ FAST cin>>r>>c>>n; FOR(i,1,n){ cin>>A[i].f>>A[i].s; d.eb(A[i].f), d.eb(A[i].f+1), dc.eb(A[i].s); } sort(all(d)), d.resize(unique(all(d))-d.begin()); sort(all(dc)), dc.resize(unique(all(dc))-dc.begin()); FOR(i,1,n){ row[lbd(d,A[i].f)].eb(A[i].s, i*2-1); row[lbd(d,A[i].f+1)].eb(A[i].s, i*2); col[lbd(dc,A[i].s)].eb(i*2-1,i*2); } FOR(ii,0,siz(d)-1){ sort(all(row[ii]),[](pi x,pi y){if(x.f^y.f)return x.f<y.f;else return (x.s+1&1) < (y.s+1&1);}); FOR(i,0,siz(row[ii])-2){ col[lbd(dc,row[ii][i].f)].eb(row[ii][i].s,row[ii][i+1].s); } } FOR(i,0,MAXN-1)p[i]=i; cin>>q; FOR(i,1,q){ ll a,b,x,y; cin>>a>>b>>x>>y; auto exist=[&](ll a,ll b){ ll pos1=lbd(d,a); if(pos1==d.size()||d[pos1]!=a)return 0; ll pos2=lbd(d,b); if(pos2==d.size()||d[pos2]!=b)return 0; return int(pos2-pos1==b-a); }; if(a>x||((!exist(a,x))&&a!=x)||b>y) ans[i]=0; else if(a==x) ans[i]=1; else { ll p1=lbd(d,a),p2=lbd(d,x); pos[i].f=lbd(row[p1],pi(b,0)); pos[i].s=ubd(row[p2],pi(y,LLINF))-1; if(pos[i].f==row[p1].size()||pos[i].s<0){ ans[i]=0; continue; } pos[i].f=row[p1][pos[i].f].s, pos[i].s=row[p2][pos[i].s].s; Q.eb(-i,pi(a,b)); Q.eb(i,pi(x,y)); } } sort(all(Q),[](spi x,spi y){return pi(-x.s.s,x.f)<pi(-y.s.s,y.f);}); ll pre=siz(dc); for(auto i:Q){ i.s.s=lbd(dc,i.s.s); while(pre>i.s.s){ -- pre; for(auto j:col[pre]){ merge(j.f,j.s); } } if(i.f<0){ i.f*=-1; ans[i.f]=same(pos[i.f].f,pos[i.f].s); } } FOR(i,1,q)cout<<(ans[i]?"YES":"NO")<<'\n'; }

Compilation message (stderr)

trampoline.cpp: In lambda function:
trampoline.cpp:55:77: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   sort(all(row[ii]),[](pi x,pi y){if(x.f^y.f)return x.f<y.f;else return (x.s+1&1) < (y.s+1&1);});
                                                                          ~~~^~
trampoline.cpp:55:89: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   sort(all(row[ii]),[](pi x,pi y){if(x.f^y.f)return x.f<y.f;else return (x.s+1&1) < (y.s+1&1);});
                                                                                      ~~~^~
trampoline.cpp: In lambda function:
trampoline.cpp:67:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pos1==d.size()||d[pos1]!=a)return 0;
       ~~~~^~~~~~~~~~
trampoline.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pos2==d.size()||d[pos2]!=b)return 0;
       ~~~~^~~~~~~~~~
trampoline.cpp: In function 'int main()':
trampoline.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pos[i].f==row[p1].size()||pos[i].s<0){
       ~~~~~~~~^~~~~~~~~~~~~~~~
#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...