Submission #29181

#TimeUsernameProblemLanguageResultExecution timeMemory
29181samir_droubiMostovi (COI14_mostovi)C++14
0 / 100
339 ms8624 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) { return true; if(blk1.empty())return false; 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) { return true; if(blk2.empty())return false; 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) { return {-1,-1}; if(b1.empty())return {-1,-1}; 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) { return {-1,-1}; if(b2.empty())return {-1,-1}; map<int,int>::iterator it = b2.upper_bound(x); if( it == b2.begin() )return {-1,-1}; --it; return { it->first , it->second }; } pair<int,int> prev_bridge1(int x) { return {-1,-1}; if(b1.empty())return {-1,-1}; map<int,int>::iterator it = b1.upper_bound(x); if( it == b1.begin() )return { -1 , -1 }; --it; return { it->first , it->second }; } pair<int,int> prev_bridge2(int x) { return {-1,-1}; if(b2.empty())return {-1,-1}; map<int,int>::iterator it = b2.lower_bound(x); if( it == b2.end() )return { -1 , -1 }; return { it->first , it->second }; } bool check1(int x,int y) { return true; pair<int,int> p = next_bridge1(x); pair<int,int> pp = prev_bridge2(y); return (p.first!=-1 && p.second >= y && !blocked1( x, p.first) && !blocked2( p.second, y) ) || (pp.first!=-1 && pp.second >= x && !blocked1( x, pp.second) && !blocked2( pp.first, y)); } bool check2(int x,int y) { return true; pair<int,int> p = next_bridge2(x); pair<int,int> pp = prev_bridge1(y); return (p.first!=-1 && p.second <=y && !blocked2( x, p.first) && !blocked1( p.second, y) ) || (pp.first!=-1 && pp.second <= x && !blocked2( x, pp.second) && !blocked1( pp.first, 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:120: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:126: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...