oj.uz

답안 #65699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65699 2018-08-08T12:20:11 Z knon0501 조화행렬 (KOI18_matrix) C++14
9 / 100
 3242 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)u=g(y,mid+1,r,seg[lv].rr);
    }
    if(seg[lv].ll!=0) 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)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 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

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

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 16180 KB Output is correct
2 Correct 56 ms 16180 KB Output is correct
3 Correct 79 ms 22428 KB Output is correct
4 Correct 146 ms 26720 KB Output is correct
5 Correct 63 ms 26720 KB Output is correct
6 Correct 53 ms 26720 KB Output is correct
7 Correct 129 ms 26724 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 16180 KB Output is correct
2 Correct 56 ms 16180 KB Output is correct
3 Correct 79 ms 22428 KB Output is correct
4 Correct 146 ms 26720 KB Output is correct
5 Correct 63 ms 26720 KB Output is correct
6 Correct 53 ms 26720 KB Output is correct
7 Correct 129 ms 26724 KB Output is correct
8 Correct 1625 ms 423256 KB Output is correct
9 Correct 2970 ms 574440 KB Output is correct
10 Correct 1333 ms 574440 KB Output is correct
11 Correct 1373 ms 574440 KB Output is correct
12 Runtime error 3242 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 -