Submission #64863

#	Time	Username	Problem	Language	Result	Execution time	Memory
64863		gs18115	조화행렬 (KOI18_matrix)	C++14	23 / 100	48 ms	21536 KiB

matrix

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int INF=1e9;
struct matrix
{
    int x,y,z;
    matrix()
    {
        x=y=z=0;
    }
}mat[123456];
bool cmp1(matrix a,matrix b)
{
    return a.x<b.x;
}
bool cmp2(matrix a,matrix b)
{
    return a.y<b.y;
}
bool cmp3(matrix a,matrix b)
{
    return a.z<b.z;
}
set<pair<int,int> >S[123456];
bool fp(int x,int y,int k)
{
    set<pair<int,int> >::iterator it=lower_bound(S[k].begin(),S[k].end(),make_pair(x,-INF));
    if(it==S[k].begin())
        return false;
    it--;
    if(it->second>y)
        return false;
    return true;
}
void ap(int x,int y,int k)
{
    if(fp(x,y,k))
        return;
    while(true)
    {
        set<pair<int,int> >::iterator it=lower_bound(S[k].begin(),S[k].end(),make_pair(x,INF));
        if(it->second>y)
            S[k].erase(it);
        else
            break;
    }
    S[k].insert(make_pair(x,y));
    return;
}
int M,N,i;
int maxi,s,e,mid;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>M>>N;
    for(i=0;i<N;i++)
        cin>>mat[i].x;
    for(i=0;i<N;i++)
        cin>>mat[i].y;
    for(i=0;i<N;i++)
    {
        if(M==2)
            mat[i].z=mat[i].y;
        else
            cin>>mat[i].z;
    }
    sort(mat,mat+N,cmp2);
    for(i=0;i<N;i++)
        mat[i].y=i+1;
    sort(mat,mat+N,cmp3);
    for(i=0;i<N;i++)
        mat[i].z=i+1;
    sort(mat,mat+N,cmp1);
    ap(0,0,0);
    maxi=1;
    for(i=0;i<N;i++)
    {
        s=0;e=maxi;
        while(s<e)
        {
            mid=s+e+1>>1;
            if(fp(mat[i].y,mat[i].z,mid))
                s=mid;
            else
                e=mid-1;
        }
        if(s+2>maxi)
            maxi=s+2;
        ap(mat[i].y,mat[i].z,s+1);
    }
    cout<<maxi-1;
    return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:86:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             mid=s+e+1>>1;
                 ~~~^~

• Subtask 1: 14 / 14
• Subtask 2: 9 / 9
• Subtask 3: 0 / 15
• Subtask 4: 0 / 62