Submission #64870

#	Time	Username	Problem	Language	Result	Execution time	Memory
64870		gs18115	조화행렬 (KOI18_matrix)	C++14	100 / 100	515 ms	119632 KiB

matrix

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int INF=1e9;
const int MAXN=2e5+10;
struct matrix
{
    int x,y,z;
    matrix()
    {
        x=y=z=0;
    }
}mat[MAXN];
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[MAXN];
bool fp(int x,int y,int k)
{
    set<pair<int,int> >::iterator it=S[k].lower_bound(make_pair(x,0));
    if(it==S[k].begin())
        return false;
    it--;
    return it->second<y;
}
void ap(int x,int y,int k)
{
    if(fp(x,y,k))
        return;
    while(true)
    {
        set<pair<int,int> >::iterator it=S[k].lower_bound(make_pair(x,0));
        if(it==S[k].end())
            break;
        else 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;
    if(M==2)
        for(i=0;i<N;i++)
            mat[i].z=mat[i].y;
    else
        for(i=0;i<N;i++)
            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(mat[0].y,mat[0].z,1);
    maxi=1;
    for(i=1;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>=maxi)
            maxi=s+1;
        ap(mat[i].y,mat[i].z,s+1);
    }
    cout<<maxi;
    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: 15 / 15
• Subtask 4: 62 / 62