답안 #29144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29144	2017-07-18T11:36:41 Z	samir_droubi	Mostovi (COI14_mostovi)	C++14	60 / 100	589 ms	11004 KB

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

Subtask #1

60.0 / 100.0

#	결과	실행 시간	메모리	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)