oj.uz

Submission #65188

# Submission time Handle Problem Language Result Execution time Memory
65188 2018-08-07T01:23:55 Z red1108 None (KOI18_matrix) C++17
0 / 100
 4000 ms 30584 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 26364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 28008 KB Output is correct
2 Correct 1591 ms 28652 KB Output is correct
3 Correct 180 ms 28652 KB Output is correct
4 Correct 136 ms 28652 KB Output is correct
5 Correct 215 ms 28652 KB Output is correct
6 Execution timed out 4024 ms 30584 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 26364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 28008 KB Output is correct
2 Correct 1591 ms 28652 KB Output is correct
3 Correct 180 ms 28652 KB Output is correct
4 Correct 136 ms 28652 KB Output is correct
5 Correct 215 ms 28652 KB Output is correct
6 Execution timed out 4024 ms 30584 KB Time limit exceeded
7 Halted 0 ms 0 KB -