oj.uz

Submission #65551

# Submission time Handle Problem Language Result Execution time Memory
65551 2018-08-08T01:05:51 Z red1108 None (KOI18_matrix) C++17
100 / 100
 2309 ms 314204 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 40 ms 26232 KB Output is correct
2 Correct 43 ms 26468 KB Output is correct
3 Correct 43 ms 26468 KB Output is correct
4 Correct 42 ms 26468 KB Output is correct
5 Correct 40 ms 26468 KB Output is correct
6 Correct 59 ms 26468 KB Output is correct
7 Correct 44 ms 26468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 27900 KB Output is correct
2 Correct 72 ms 28620 KB Output is correct
3 Correct 55 ms 28620 KB Output is correct
4 Correct 69 ms 28620 KB Output is correct
5 Correct 58 ms 28620 KB Output is correct
6 Correct 65 ms 32604 KB Output is correct
7 Correct 75 ms 32604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 26232 KB Output is correct
2 Correct 43 ms 26468 KB Output is correct
3 Correct 43 ms 26468 KB Output is correct
4 Correct 42 ms 26468 KB Output is correct
5 Correct 40 ms 26468 KB Output is correct
6 Correct 59 ms 26468 KB Output is correct
7 Correct 44 ms 26468 KB Output is correct
8 Correct 650 ms 46876 KB Output is correct
9 Correct 534 ms 46964 KB Output is correct
10 Correct 379 ms 46988 KB Output is correct
11 Correct 419 ms 47140 KB Output is correct
12 Correct 417 ms 47140 KB Output is correct
13 Correct 500 ms 47140 KB Output is correct
14 Correct 423 ms 47140 KB Output is correct
15 Correct 527 ms 47140 KB Output is correct
16 Correct 452 ms 47140 KB Output is correct
17 Correct 575 ms 47140 KB Output is correct
18 Correct 451 ms 47140 KB Output is correct
19 Correct 379 ms 47140 KB Output is correct
20 Correct 781 ms 47140 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 27900 KB Output is correct
2 Correct 72 ms 28620 KB Output is correct
3 Correct 55 ms 28620 KB Output is correct
4 Correct 69 ms 28620 KB Output is correct
5 Correct 58 ms 28620 KB Output is correct
6 Correct 65 ms 32604 KB Output is correct
7 Correct 75 ms 32604 KB Output is correct
8 Correct 1033 ms 78096 KB Output is correct
9 Correct 612 ms 78096 KB Output is correct
10 Correct 1211 ms 114160 KB Output is correct
11 Correct 1747 ms 225416 KB Output is correct
12 Correct 372 ms 225416 KB Output is correct
13 Correct 976 ms 225416 KB Output is correct
14 Correct 1201 ms 225416 KB Output is correct
15 Correct 1793 ms 238124 KB Output is correct
16 Correct 1740 ms 243736 KB Output is correct
17 Correct 534 ms 243736 KB Output is correct
18 Correct 2309 ms 243736 KB Output is correct
19 Correct 1040 ms 243736 KB Output is correct
20 Correct 1006 ms 243736 KB Output is correct
21 Correct 1822 ms 273760 KB Output is correct
22 Correct 2223 ms 273760 KB Output is correct
23 Correct 518 ms 273760 KB Output is correct
24 Correct 860 ms 273760 KB Output is correct
25 Correct 1658 ms 273760 KB Output is correct
26 Correct 603 ms 273760 KB Output is correct
27 Correct 318 ms 273760 KB Output is correct
28 Correct 1761 ms 314204 KB Output is correct
29 Correct 515 ms 314204 KB Output is correct
30 Correct 531 ms 314204 KB Output is correct
31 Correct 580 ms 314204 KB Output is correct
32 Correct 563 ms 314204 KB Output is correct