oj.uz

Submission #65548

# Submission time Handle Problem Language Result Execution time Memory
65548 2018-08-08T00:51:39 Z red1108 None (KOI18_matrix) C++17
29 / 100
 4000 ms 100260 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=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 pos, int curz, int put)
{
    pos=pos+si-1;
    while(pos)
    {
        auto it=lower_bound(seg[pos].begin(),seg[pos].end(),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 56 ms 26488 KB Output is correct
2 Correct 50 ms 26776 KB Output is correct
3 Correct 46 ms 26952 KB Output is correct
4 Correct 57 ms 27228 KB Output is correct
5 Correct 66 ms 27520 KB Output is correct
6 Correct 53 ms 27776 KB Output is correct
7 Correct 57 ms 27948 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 29768 KB Output is correct
2 Correct 1699 ms 30912 KB Output is correct
3 Correct 141 ms 30912 KB Output is correct
4 Correct 127 ms 30912 KB Output is correct
5 Correct 222 ms 30912 KB Output is correct
6 Execution timed out 4045 ms 33744 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 26488 KB Output is correct
2 Correct 50 ms 26776 KB Output is correct
3 Correct 46 ms 26952 KB Output is correct
4 Correct 57 ms 27228 KB Output is correct
5 Correct 66 ms 27520 KB Output is correct
6 Correct 53 ms 27776 KB Output is correct
7 Correct 57 ms 27948 KB Output is correct
8 Correct 898 ms 53816 KB Output is correct
9 Correct 636 ms 57628 KB Output is correct
10 Correct 447 ms 61396 KB Output is correct
11 Correct 543 ms 65296 KB Output is correct
12 Correct 528 ms 69396 KB Output is correct
13 Correct 545 ms 73232 KB Output is correct
14 Correct 456 ms 77156 KB Output is correct
15 Correct 505 ms 80864 KB Output is correct
16 Correct 583 ms 84772 KB Output is correct
17 Correct 718 ms 88636 KB Output is correct
18 Correct 583 ms 92516 KB Output is correct
19 Correct 445 ms 96524 KB Output is correct
20 Correct 802 ms 100260 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 29768 KB Output is correct
2 Correct 1699 ms 30912 KB Output is correct
3 Correct 141 ms 30912 KB Output is correct
4 Correct 127 ms 30912 KB Output is correct
5 Correct 222 ms 30912 KB Output is correct
6 Execution timed out 4045 ms 33744 KB Time limit exceeded
7 Halted 0 ms 0 KB -