글 읽기 - 도와주세요..반례를 구합니다..

wise0926 4년 전 0

세그먼트로 구현해서 2 시험 등수 인덱스에 3번째 등수를 넣는 방식으로 했습니다... 도와주세요..

#include <stdio.h>
#include <algorithm>
using namespace std;
struct func{
    int a,b,c;
};
func f[11111111];
bool cmp(func aa,func bb) {
    return aa.a<bb.a;
}
int min(int a,int b) {
    return (a>b) ? b : a;
}
int tree[11111111];
int main()
{
    int n;
    int cnt=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int s;
        scanf("%d",&s);
        f[s].a=i;
    }
    for(int i=1;i<=n;i++) {
        int s;
        scanf("%d",&s);
        f[s].b=i;
    }
    for(int i=1;i<=n;i++) {
        int s;
        scanf("%d",&s);
        f[s].c=i;
    }
    tree[0]=2e9;
    sort(f+1,f+1+n,cmp);
    int a=1;
    int check=0;
    while(a<n) a*=2;
    for(int i=1;i<=a+n+1;i++) tree[i]=2e9;
    for(int i=1;i<=n;i++) {
        tree[f[i].b+a-1]=f[i].c;
        int x=a;
        int y=f[i].b+a-1;
        int w=f[i].c;
        if(y%2==1) {
            if(tree[y-1]<w) continue;
        }
        while(x<y-1) {
            if(y%2==0) {
                tree[y/2]=min(tree[y],tree[y+1]);
                y/=2;
            }
            else {
                tree[y/2]=min(tree[y],tree[y-1]);
                y/=2;
            }
            x/=2;
        }
        if(tree[x]>w){
             cnt++;
             //printf("%d",i);
        }
        /*if(y==x) {
            tree[y]=w;
        }*/
        //for(int i=1;i<=a+n;i++) printf("%d ",tree[i]);
        printf("\n");
        while(x>1) {
            tree[x/2]=min(tree[x],tree[y]);
            x/=2;
            y+=1;
            y/=2;
        }
    }
    printf("%d",cnt);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와주세요..반례를 구합니다..

wise0926 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말