oj.uz

답안 #65701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65701 2018-08-08T12:28:46 Z knon0501 조화행렬 (KOI18_matrix) C++17
9 / 100
 4000 ms 489668 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;
int num2;
set<int> S1;
set<int> S2;

struct Tree{
    int l,r,w;
}seg[MX*40];
struct Real{
    int l,r,d;
}seg2[MX*600];

inline int max2(int x,int y){
    return x>y ?x:y;
}
int g(int y,int l,int r,int lv){
    if(l>=y)return 0;
    if(r<y)return seg2[lv].d;
    int u=0,v=0;
    int mid=(l+r)/2;
    if(y>mid){
        if(seg2[lv].r!=0)u=g(y,mid+1,r,seg2[lv].r);
    }
    if(seg2[lv].l!=0) v=g(y,l,mid,seg2[lv].l);
    return max2(u,v);
}
int f(int x,int y,int l,int r,int lv){
    if(l>=x)return 0;
    if(r<x){
        if(seg[lv].w==0)return 0;
        return g(y,1,nn,seg[lv].w);
    }
    int u=0,v=0;
    int mid=(l+r)/2;
    if(x>mid){
        if(seg[lv].r!=0)u=f(x,y,mid+1,r,seg[lv].r);
    }
    if(seg[lv].l!=0)v=f(x,y,l,mid,seg[lv].l);
    return max2(u,v);
}

void update2(int y,int l,int r,int lv,int k){
    seg2[lv].d=max2(seg2[lv].d,k);
    int mid=(l+r)/2;
    if(l==r)return;
    if(y>mid){
        if(seg2[lv].r==0)seg2[lv].r=++num2;
        update2(y,mid+1,r,seg2[lv].r,k);
    }
    else{
        if(seg2[lv].l==0)seg2[lv].l=++num2;
        update2(y,l,mid,seg2[lv].l,k);
    }
}
void update(int x,int y,int l,int r,int lv,int 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);
        }
    }
    if(seg[lv].w==0)seg[lv].w=++num2;
    update2(y,1,nn,seg[lv].w,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=max2(ans,k);
    }


    cout<<ans;
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 10728 KB Output is correct
2 Correct 52 ms 10728 KB Output is correct
3 Correct 69 ms 14032 KB Output is correct
4 Correct 103 ms 16392 KB Output is correct
5 Correct 53 ms 16392 KB Output is correct
6 Correct 44 ms 16392 KB Output is correct
7 Correct 90 ms 16392 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 10728 KB Output is correct
2 Correct 52 ms 10728 KB Output is correct
3 Correct 69 ms 14032 KB Output is correct
4 Correct 103 ms 16392 KB Output is correct
5 Correct 53 ms 16392 KB Output is correct
6 Correct 44 ms 16392 KB Output is correct
7 Correct 90 ms 16392 KB Output is correct
8 Correct 1494 ms 271828 KB Output is correct
9 Correct 2837 ms 360936 KB Output is correct
10 Correct 1236 ms 360936 KB Output is correct
11 Correct 1253 ms 360936 KB Output is correct
12 Correct 2614 ms 489668 KB Output is correct
13 Correct 1380 ms 489668 KB Output is correct
14 Correct 2929 ms 489668 KB Output is correct
15 Correct 1246 ms 489668 KB Output is correct
16 Correct 1296 ms 489668 KB Output is correct
17 Correct 2667 ms 489668 KB Output is correct
18 Execution timed out 4070 ms 489668 KB Time limit exceeded
19 Halted 0 ms 0 KB -