oj.uz

Submission #65695

# Submission time Handle Problem Language Result Execution time Memory
65695 2018-08-08T12:09:34 Z knon0501 None (KOI18_matrix) C++17
9 / 100
 3978 ms 787456 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];
map<int,int> xx;
map<int,int> yy;
long long nn;
int ans;
int num;
set<int> S1;
set<int> S2;

struct Tree{
    int l,r,ll,rr,d;
}seg[MX*500];

int g(int y,int l,int r,int lv){
    if(l>=y)return 0;
    if(r<y)return seg[lv].d;
    int u=0,v=0;
    int mid=(l+r)/2;
    if(y>mid){
        if(seg[lv].rr==0)seg[lv].rr=++num;
        else u=g(y,mid+1,r,seg[lv].rr);
    }
    if(seg[lv].ll==0)seg[lv].ll=++num;
    else
        v=g(y,l,mid,seg[lv].ll);
    return max(u,v);
}
int f(int x,int y,int l,int r,int lv){
    if(l>=x)return 0;
    if(r<x)return g(y,1,nn,lv);
    int u=0,v=0;
    int mid=(l+r)/2;
    if(x>mid){
        if(seg[lv].r==0)seg[lv].r=++num;
        else u=f(x,y,mid+1,r,seg[lv].r);
    }
    if(seg[lv].l==0)seg[lv].l=++num;
    else v=f(x,y,l,mid,seg[lv].l);
    return max(u,v);
}

void update2(int y,int l,int r,int lv,int k){
    seg[lv].d=max(seg[lv].d,k);
    int mid=(l+r)/2;
    if(l==r)return;
    if(y>mid){
        if(seg[lv].rr==0)seg[lv].rr=++num;
        update2(y,mid+1,r,seg[lv].rr,k);
    }
    else{
        if(seg[lv].ll==0)seg[lv].ll=++num;
        update2(y,l,mid,seg[lv].ll,k);
    }
}
void update(int x,int y,int l,int r,int lv,int k){
    seg[lv].d=max(seg[lv].d,k);
    int mid=(l+r)/2;
    if(l!=r){
        if(x>mid){
            if(seg[lv].r==0)seg[lv].r=++num;
            update(x,y,mid+1,r,seg[lv].r,k);
        }
        else{
            if(seg[lv].l==0)seg[lv].l=++num;
            update(x,y,l,mid,seg[lv].l,k);
        }
    }
    update2(y,1,nn,lv,k);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n;

    int i;
    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);

    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;
    ++num;
    for(i=1 ; i<=n ; i++){
        tx=xx[a[i].s.f];
        ty=yy[a[i].s.s];
        k=f(tx,ty,1,nn,1)+1;
        update(tx,ty,1,nn,1,k);
        ans=max(ans,k);
    }


    cout<<ans;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 7416 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 65 ms 17816 KB Output is correct
2 Correct 52 ms 17816 KB Output is correct
3 Correct 83 ms 23868 KB Output is correct
4 Correct 130 ms 27820 KB Output is correct
5 Correct 68 ms 27820 KB Output is correct
6 Correct 54 ms 27820 KB Output is correct
7 Correct 108 ms 27820 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 17816 KB Output is correct
2 Correct 52 ms 17816 KB Output is correct
3 Correct 83 ms 23868 KB Output is correct
4 Correct 130 ms 27820 KB Output is correct
5 Correct 68 ms 27820 KB Output is correct
6 Correct 54 ms 27820 KB Output is correct
7 Correct 108 ms 27820 KB Output is correct
8 Correct 1843 ms 467752 KB Output is correct
9 Correct 3590 ms 607716 KB Output is correct
10 Correct 1606 ms 607716 KB Output is correct
11 Correct 1469 ms 607716 KB Output is correct
12 Runtime error 3978 ms 787456 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
13 Halted 0 ms 0 KB -