Submission #65188

#	Time	Username	Problem	Language	Result	Execution time	Memory
65188		red1108	조화행렬 (KOI18_matrix)	C++17	0 / 100	4024 ms	30584 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
struct in{
    int x, y,z;
}input[200010];
int n, k,si=1;
set<pair<int,int> > seg[530000];
vector<pair<int,int> > er;
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=upper_bound(seg[cur].begin(),seg[cur].end(),pair<int,int>{zz,0});
        if(it==seg[cur].begin())
        {
            if((*it).first<=zz) return (*it).second;
            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 cury, int curz, int put)
{
    cury=cury+si-1;
    while(cury)
    {
        auto it=lower_bound(seg[cury].begin(),seg[cury].end(),pair<int,int>{curz,0});
        if(it!=seg[cury].begin())
        {
            it--;
            if((*it).second>=put) break;
            it++;
        }
        er.clear();
        while(it!=seg[cury].end()&&(*it).second<=put)
        {
            er.push_back({(*it).first,(*it).second});
            it++;
        }
        for(auto i:er)seg[cury].erase(i);
        seg[cury].insert({curz,put});
        cury/=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:51: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:52: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:53: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:54: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: 0 / 14
• Subtask 2: 0 / 9
• Subtask 3: 0 / 15
• Subtask 4: 0 / 62