oj.uz

Submission #65216

# Submission time Handle Problem Language Result Execution time Memory
65216 2018-08-07T05:12:53 Z red1108 None (KOI18_matrix) C++17
29 / 100
 4000 ms 76380 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,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 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,-put});
        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:47: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:48: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: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].y);
                       ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:50: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 47 ms 26232 KB Output is correct
2 Correct 42 ms 26344 KB Output is correct
3 Correct 41 ms 26420 KB Output is correct
4 Correct 40 ms 26420 KB Output is correct
5 Correct 57 ms 26444 KB Output is correct
6 Correct 47 ms 26496 KB Output is correct
7 Correct 54 ms 26552 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 28044 KB Output is correct
2 Correct 1656 ms 28780 KB Output is correct
3 Correct 163 ms 28780 KB Output is correct
4 Correct 120 ms 28780 KB Output is correct
5 Correct 206 ms 28780 KB Output is correct
6 Execution timed out 4056 ms 30524 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 26232 KB Output is correct
2 Correct 42 ms 26344 KB Output is correct
3 Correct 41 ms 26420 KB Output is correct
4 Correct 40 ms 26420 KB Output is correct
5 Correct 57 ms 26444 KB Output is correct
6 Correct 47 ms 26496 KB Output is correct
7 Correct 54 ms 26552 KB Output is correct
8 Correct 836 ms 46800 KB Output is correct
9 Correct 666 ms 50556 KB Output is correct
10 Correct 468 ms 54512 KB Output is correct
11 Correct 446 ms 58184 KB Output is correct
12 Correct 669 ms 60476 KB Output is correct
13 Correct 588 ms 60476 KB Output is correct
14 Correct 469 ms 60476 KB Output is correct
15 Correct 496 ms 60476 KB Output is correct
16 Correct 556 ms 61336 KB Output is correct
17 Correct 512 ms 65252 KB Output is correct
18 Correct 458 ms 69000 KB Output is correct
19 Correct 415 ms 73004 KB Output is correct
20 Correct 880 ms 76380 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 28044 KB Output is correct
2 Correct 1656 ms 28780 KB Output is correct
3 Correct 163 ms 28780 KB Output is correct
4 Correct 120 ms 28780 KB Output is correct
5 Correct 206 ms 28780 KB Output is correct
6 Execution timed out 4056 ms 30524 KB Time limit exceeded
7 Halted 0 ms 0 KB -