oj.uz

답안 #65688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65688 2018-08-08T12:02:22 Z knon0501 조화행렬 (KOI18_matrix) C++14
9 / 100
 4000 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*400];

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;
        u=g(y,mid+1,r,seg[lv].rr);
    }
    if(seg[lv].ll==0)seg[lv].ll=++num;
    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;
        u=f(x,y,mid+1,r,seg[lv].r);
    }
    if(seg[lv].l==0)seg[lv].l=++num;
    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,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);

    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=ans>k?ans:k;
    }


    cout<<ans;
    return 0;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:81:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;
           ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 20892 KB Output is correct
2 Correct 59 ms 20892 KB Output is correct
3 Correct 114 ms 30056 KB Output is correct
4 Correct 158 ms 36768 KB Output is correct
5 Correct 89 ms 36768 KB Output is correct
6 Correct 63 ms 36768 KB Output is correct
7 Correct 181 ms 36768 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 20892 KB Output is correct
2 Correct 59 ms 20892 KB Output is correct
3 Correct 114 ms 30056 KB Output is correct
4 Correct 158 ms 36768 KB Output is correct
5 Correct 89 ms 36768 KB Output is correct
6 Correct 63 ms 36768 KB Output is correct
7 Correct 181 ms 36768 KB Output is correct
8 Correct 1989 ms 571128 KB Output is correct
9 Execution timed out 4127 ms 787456 KB Time limit exceeded
10 Halted 0 ms 0 KB -