oj.uz

Submission #65461

# Submission time Handle Problem Language Result Execution time Memory
65461 2018-08-07T16:05:20 Z knon0501 None (KOI18_matrix) C++14
9 / 100
 1460 ms 59932 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,m;
const int MX=2e5+5;
pair<int,pair<int,int>> a[MX];
unordered_map<long long,int> seg;
unordered_map<int,int> xx;
unordered_map<int,int> yy;
long long nn;
int ans;
int p;
stack<int> S;
inline int g(int y,int lev1){
    S.push(1);
    S.push(nn);
    S.push(1);
    int k=0;
    while(!S.empty()){
        int lv=S.top();S.pop();
        int r=S.top();S.pop();
        int l=S.top();S.pop();
        if(l>=y)continue;
        if(r<y)k=max(k,seg[nn*2*lev1+lv]);
        else{
            if(y>(l+r)/2+1){
                k=max(k,seg[nn*2*lev1+lv*2]);
                S.push((l+r)/2+1);
                S.push(r);
                S.push(lv*2+1);
            }
            else{
                S.push(l);
                S.push((l+r)/2);
                S.push(lv*2);
            }
        }
    }
    return k;
}
inline int f(int x,int y){

    S.push(1);
    S.push(nn);
    S.push(1);
    int k=0;
    while(!S.empty()){
        int lv=S.top();S.pop();
        int r=S.top();S.pop();
        int l=S.top();S.pop();
        if(l>=x)continue;
        if(r<x)k=max(k,g(y,lv));
        else{

            if(x>(l+r)/2+1){
                k=max(k,g(y,lv*2));
                S.push((l+r)/2+1);
                S.push(r);
                S.push(lv*2+1);
            }
            else{
                S.push(l);
                S.push((l+r)/2);
                S.push(lv*2);
            }
        }
    }
    return k;
}
void process(){
    int i,j;
    for(nn=1 ; nn<n ; nn*=2);

    for(i=1 ; i<=n ; i++)cin>>a[i].f;
    for(i=1 ; i<=n ; i++)cin>>a[i].s.f;
    for(i=1 ; i<=n ; i++)cin>>a[i].s.s;
    sort(a+1,a+n+1);
    set<int> S1;
    set<int> S2;
    for(i=1 ; i<=n ; i++){
        S1.insert(a[i].s.f);
        S2.insert(a[i].s.s);
    }
    int cnt=0;
    for(auto &i:S1)xx[i]=++cnt;
    cnt=0;
    for(auto &i:S2)yy[i]=++cnt;

    int tx,ty,k;
    for(int ii=1 ; ii<=n ; ii++){
        tx=xx[a[ii].s.f];
        ty=yy[a[ii].s.s];
        if(n<=10000){
            k=f(tx,ty)+1;
        }
        for(i=nn+tx-1 ; i>=1 ; i/=2){
            for(j=nn+ty-1 ; j>=1 ; j/=2)
                if(n>10000)k=k*k*k*k*k;
                else{

                if(seg[nn*2*i+j]<k)
                    seg[nn*2*i+j]=k;
                else
                    break;
                }
        }

        ans=ans>k?ans:k;

    }

    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n;
    if(m==3)process();
    return 0;
}

Compilation message

matrix.cpp: In function 'void process()':
matrix.cpp:103:34: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
                     seg[nn*2*i+j]=k;

Subtask #1
0 / 14.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 34600 KB Output is correct
2 Correct 472 ms 34600 KB Output is correct
3 Correct 1168 ms 52484 KB Output is correct
4 Correct 1460 ms 59932 KB Output is correct
5 Correct 986 ms 59932 KB Output is correct
6 Correct 540 ms 59932 KB Output is correct
7 Correct 1312 ms 59932 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 34600 KB Output is correct
2 Correct 472 ms 34600 KB Output is correct
3 Correct 1168 ms 52484 KB Output is correct
4 Correct 1460 ms 59932 KB Output is correct
5 Correct 986 ms 59932 KB Output is correct
6 Correct 540 ms 59932 KB Output is correct
7 Correct 1312 ms 59932 KB Output is correct
8 Incorrect 877 ms 59932 KB Output isn't correct
9 Halted 0 ms 0 KB -