Submission #29089

#TimeUsernameProblemLanguageResultExecution timeMemory
29089samir_droubiMostovi (COI14_mostovi)C++14
30 / 100
1000 ms2024 KiB
#include <bits/stdc++.h> using namespace std; int n; int m; set<int>blk1; set<int>blk2; map<int,int>b1; map<int,int>b2; bool blocked1(int x,int y) { set<int>::iterator it = blk1.upper_bound(x); if( it == blk1.end() )return false; if(*it <= y)return true; return false; } bool blocked2(int x,int y) { set<int>::iterator it = blk2.upper_bound(x); if( it == blk2.begin() )return false; --it; if( *it > y )return true; return false; } pair<int,int> next_bridge1(int x) { map<int,int>::iterator it = b1.lower_bound(x); if( it == b1.end( ))return { -1 , -1 }; return { it->first , it->second }; } pair<int,int> next_bridge2(int x) { map<int,int>::iterator it = b2.upper_bound(x); if( it == b2.begin() )return {-1,-1}; --it; return { it->first , it->second }; } bool check1(int x,int y) { int l = x; int r = n; pair<int,int> ans = { -1 , -1 }; while( l <= r ) { int md = ( l + r ) / 2; pair<int,int> p = next_bridge1(md); if( p.first == -1 ) r = md - 1 ; else { if( p.second >= y ) { ans = p; r = md - 1; } else l = md + 1; } } if( ans.first == -1 )return false; return !blocked1( x, ans.first) && !blocked2( ans.second, y); } bool check2(int x,int y) { int l = n + 1; int r = x; pair<int,int> ans = { -1 , -1 }; while( l <= r ) { int md = ( l + r ) / 2; pair<int,int> p = next_bridge2(md); if( p.first == -1 )l = md + 1; else { if( p.second <= y ) { ans = p; l = md + 1; } else r = md - 1; } } if( ans.first == -1 )return false; return !blocked2( x, ans.first) && !blocked1( ans.second, y); } bool check(int x,int y) { if( x <= n && y <= n ) { if( x < y) return !blocked1( x, y); else { pair<int,int> p = next_bridge1(x); if( p.first == -1 )return false; return !blocked1( x, p.first) && check2( p.second, y); } } else if( x > n && y > n ) { if( x > y ) return !blocked2( x, y); else { pair<int,int> p = next_bridge2(x); if( p.first == -1 )return false; return !blocked2( x, p.first) && check1( p.second, y); } } else { if(x <= n)return check1( x, y); else return check2( x, y); } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;++i) { char c; cin>>c; int x,y; scanf("%d%d",&x,&y); if(c=='A') { if(x <= n) { b1[x]=y; b2[y]=x; } else { b1[y]=x; b2[x]=y; } } if(c=='B') { if(x <= n)blk1.insert(max(x,y)); else blk2.insert(max(x,y)); } if(c=='Q') { if(check(x,y))puts("DA"); else puts("NE"); } } return 0; }

Compilation message (stderr)

mostovi.cpp: In function 'int main()':
mostovi.cpp:115:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
mostovi.cpp:121:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...