Submission #65551

#	Time	Username	Problem	Language	Result	Execution time	Memory
65551		red1108	조화행렬 (KOI18_matrix)	C++17	100 / 100	2309 ms	314204 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
struct in{
    int x, y,z;
}input[200010];
int n, k,si=1,top=0;
set<pair<int,int> > seg[530000];
pair<int,int> er[200010];
int getmax(int cur, int l, int r, int s, int e, int zz)
{
    if(l>r||r<s||e<l) return 0;
    if(s<=l&&r<=e)
    {
        auto it=seg[cur].lower_bound(pair<int,int>{zz,1000000});
        if(it==seg[cur].begin()) return 0;
        it--;
        return -(*it).second;
    }
    return max(getmax(cur*2,l,(l+r)/2,s,e,zz),getmax(cur*2+1,(l+r)/2+1,r,s,e,zz));
}
void gang(int pos, int curz, int put)
{
    pos=pos+si-1;
    while(pos)
    {
        auto it=seg[pos].lower_bound(pair<int,int>{curz,-put});
        if(it!=seg[pos].begin())
        {
            auto tmp=it;
            it--;
            if(-(*it).second>=put) break;
            it=tmp;
        }
        top=0;
        while(it!=seg[pos].end()&&-(*it).second<=put)
        {
            er[++top]={(*it).first,(*it).second};
            it++;
        }
        for(int j=1;j<=top;j++)seg[pos].erase(er[j]);
        seg[pos].insert({curz,-put});
        pos/=2;
    }
}
int main()
{
    int i,ans=0;
    scanf("%d %d",&k,&n);
    for(i=1;i<=n;i++) scanf("%d", &input[i].x);
    for(i=1;i<=n;i++) scanf("%d", &input[i].y);
    if(k==3) for(i=1;i<=n;i++) scanf("%d", &input[i].z);
    sort(input+1,input+n+1,[&](in a, in b){return a.y<b.y;});
    for(i=1;i<=n;i++) input[i].y=i;
    if(k==3) {
        sort(input+1,input+n+1,[&](in a, in b){return a.z<b.z;});
        for(i=1;i<=n;i++) input[i].z=i;
    }
    sort(input+1,input+n+1,[&](in a, in b){return a.x<b.x;});
    for(i=1;i<=n;i++) input[i].x=i;
    while(si<n) si*=2;
    for(i=1;i<=n;i++)
    {
        int t=getmax(1,1,si,1,input[i].y,input[i].z);
        gang(input[i].y,input[i].z,t+1);
        ans=max(ans,t+1);
    }
    printf("%d",ans);
}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&k,&n);
     ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:49:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%d", &input[i].x);
                       ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:50:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%d", &input[i].y);
                       ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:51:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     if(k==3) for(i=1;i<=n;i++) scanf("%d", &input[i].z);
                                ~~~~~^~~~~~~~~~~~~~~~~~~

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