oj.uz

Submission #65182

# Submission time Handle Problem Language Result Execution time Memory
65182 2018-08-07T00:40:36 Z red1108 None (KOI18_matrix) C++17
23 / 100
 4000 ms 64648 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];
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)
    {
        int ret=0;
        for(auto it:seg[cur])
        {
            if(it.first>zz) break;
            ret=max(ret,it.second);
        }
        return ret;
    }
    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)
    {
        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:35: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:36: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:37: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:38: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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 29176 KB Output is correct
2 Correct 151 ms 29176 KB Output is correct
3 Correct 139 ms 29228 KB Output is correct
4 Correct 317 ms 29528 KB Output is correct
5 Correct 135 ms 30024 KB Output is correct
6 Correct 1356 ms 33904 KB Output is correct
7 Correct 594 ms 33904 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1752 ms 34328 KB Output is correct
2 Correct 1619 ms 34724 KB Output is correct
3 Correct 1765 ms 34860 KB Output is correct
4 Correct 658 ms 35316 KB Output is correct
5 Correct 1678 ms 35504 KB Output is correct
6 Correct 1304 ms 35836 KB Output is correct
7 Correct 1467 ms 36216 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 29176 KB Output is correct
2 Correct 151 ms 29176 KB Output is correct
3 Correct 139 ms 29228 KB Output is correct
4 Correct 317 ms 29528 KB Output is correct
5 Correct 135 ms 30024 KB Output is correct
6 Correct 1356 ms 33904 KB Output is correct
7 Correct 594 ms 33904 KB Output is correct
8 Execution timed out 4050 ms 64648 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1752 ms 34328 KB Output is correct
2 Correct 1619 ms 34724 KB Output is correct
3 Correct 1765 ms 34860 KB Output is correct
4 Correct 658 ms 35316 KB Output is correct
5 Correct 1678 ms 35504 KB Output is correct
6 Correct 1304 ms 35836 KB Output is correct
7 Correct 1467 ms 36216 KB Output is correct
8 Execution timed out 4042 ms 64648 KB Time limit exceeded
9 Halted 0 ms 0 KB -