oj.uz

답안 #65702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65702 2018-08-08T12:30:08 Z knon0501 조화행렬 (KOI18_matrix) C++17
9 / 100
 4000 ms 486936 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<int,int> xx;
unordered_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 34 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 10556 KB Output is correct
2 Correct 50 ms 10556 KB Output is correct
3 Correct 68 ms 13808 KB Output is correct
4 Correct 101 ms 16308 KB Output is correct
5 Correct 59 ms 16308 KB Output is correct
6 Correct 56 ms 16308 KB Output is correct
7 Correct 90 ms 16308 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 10556 KB Output is correct
2 Correct 50 ms 10556 KB Output is correct
3 Correct 68 ms 13808 KB Output is correct
4 Correct 101 ms 16308 KB Output is correct
5 Correct 59 ms 16308 KB Output is correct
6 Correct 56 ms 16308 KB Output is correct
7 Correct 90 ms 16308 KB Output is correct
8 Correct 1697 ms 268920 KB Output is correct
9 Correct 2658 ms 358140 KB Output is correct
10 Correct 1390 ms 358140 KB Output is correct
11 Correct 1318 ms 358140 KB Output is correct
12 Correct 2558 ms 486936 KB Output is correct
13 Correct 1507 ms 486936 KB Output is correct
14 Correct 2667 ms 486936 KB Output is correct
15 Correct 1360 ms 486936 KB Output is correct
16 Correct 1336 ms 486936 KB Output is correct
17 Correct 2682 ms 486936 KB Output is correct
18 Execution timed out 4081 ms 486936 KB Time limit exceeded
19 Halted 0 ms 0 KB -