#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 };
}
pair<int,int> prev_bridge1(int x)
{
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)
{
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)
{
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)
{
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
mostovi.cpp: In function 'int main()':
mostovi.cpp:108: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:114: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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2028 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2028 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2028 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2028 KB |
Output is correct |
| 7 |
Runtime error |
326 ms |
4932 KB |
Execution timed out (wall clock limit exceeded) |
| 8 |
Runtime error |
459 ms |
7704 KB |
Execution timed out (wall clock limit exceeded) |
| 9 |
Runtime error |
526 ms |
8364 KB |
Execution timed out (wall clock limit exceeded) |
| 10 |
Runtime error |
589 ms |
11004 KB |
Execution timed out (wall clock limit exceeded) |
