oj.uz

답안 #65692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65692 2018-08-08T12:07:02 Z knon0501 조화행렬 (KOI18_matrix) C++17
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;
        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

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

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 17948 KB Output is correct
2 Correct 58 ms 17948 KB Output is correct
3 Correct 98 ms 23608 KB Output is correct
4 Correct 134 ms 27740 KB Output is correct
5 Correct 75 ms 27740 KB Output is correct
6 Correct 54 ms 27740 KB Output is correct
7 Correct 122 ms 27740 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 17948 KB Output is correct
2 Correct 58 ms 17948 KB Output is correct
3 Correct 98 ms 23608 KB Output is correct
4 Correct 134 ms 27740 KB Output is correct
5 Correct 75 ms 27740 KB Output is correct
6 Correct 54 ms 27740 KB Output is correct
7 Correct 122 ms 27740 KB Output is correct
8 Correct 1857 ms 467632 KB Output is correct
9 Correct 3962 ms 607900 KB Output is correct
10 Correct 1646 ms 607900 KB Output is correct
11 Correct 1553 ms 607900 KB Output is correct
12 Runtime error 4000 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 -