Submission #29058

#	Time	Username	Problem	Language	Result	Execution time	Memory
29058		samir_droubi	Mostovi (COI14_mostovi)	C++14	0 / 100	1000 ms	2024 KiB

mostovi

#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(y);
    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);
                            ^

• Subtask 1: 0 / 100