답안 #12036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12036 2014-12-19T08:55:20 Z gs14004 사다리꼴 (balkan11_trapezoid) C++
45 / 100
239 ms 15476 KB
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int a[100005], b[100005], c[100005], d[100005];
int dp[100005];
int num[100005], cnt[100005], pcnt[100005];
int rcnt[100005];

struct seg{int a,b,p,i;}st[100005];
bool cmp(seg a, seg b){return a.a < b.a;}
struct seg2{int dp,a,b,p,i,num;}st2[100005];
bool cmp2(seg2 a, seg2 b){return a.b < b.b;}
bool cmp3(seg2 a, seg2 b){return a.a < b.a;}

struct rmq{
    int lim, tree[530000];
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void ins(int s, int v){
        s += lim;
        tree[s] = v;
        while(s>1){
            s >>= 1;
            tree[s] = max(tree[2*s],tree[2*s+1]);
        }
    }
    int q(int s, int e){
        s += lim;
        e += lim;
        int r = 0;
        while(s<e){
            if(s%2 == 1) r = max(r,tree[s++]);
            if(e%2 == 0) r = max(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = max(r,tree[s]);
        return r;
    }
}rmq;

struct idx{
    int lim, tree[530000];
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void ins(int s, int v){
        s += lim;
        tree[s] = v;
        while(s>1){
            s >>= 1;
            tree[s] = tree[2*s] + tree[2*s+1];
            tree[s] %= 30013;
        }
    }
    int q(int s, int e){
        s += lim;
        e += lim;
        int r = 0;
        while(s<e){
            if(s%2 == 1) r += tree[s++];
            if(e%2 == 0) r += tree[e--];
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r += tree[s];
        return r % 30013;
    }
}idx;

void input(){
    vector<int> vu, vd;
    scanf("%d",&n);
    rmq.init(2*n);
    for (int i=0; i<n; i++) {
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
        vu.push_back(a[i]);
        vu.push_back(b[i]);
        vd.push_back(c[i]);
        vd.push_back(d[i]);
    }
    sort(vu.begin(),vu.end());
    sort(vd.begin(),vd.end());
    for (int i=0; i<n; i++) {
        a[i] = (int)(lower_bound(vu.begin(),vu.end(),a[i]) - vu.begin());
        b[i] = (int)(lower_bound(vu.begin(),vu.end(),b[i]) - vu.begin());
        c[i] = (int)(lower_bound(vd.begin(),vd.end(),c[i]) - vd.begin());
        d[i] = (int)(lower_bound(vd.begin(),vd.end(),d[i]) - vd.begin());
        st[2*i] = {a[i],c[i],0,i};
        st[2*i+1] = {b[i],d[i],1,i};
    }
    sort(st,st+2*n,cmp);
}

int main(){
    input();
    for (int i=0; i<2*n; i++) {
        if(st[i].p == 0){
            dp[st[i].i] = rmq.q(0,st[i].b) + 1;
            st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
        }
        else{
            rmq.ins(st[i].b,dp[st[i].i]);
            st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
        }
    }
    int mcnt = *max_element(dp,dp+n);
    printf("%d ",mcnt);
    for (int i=0; i<n; i++) {
        cnt[dp[i]]++;
    }
    for (int i=1; i<=n; i++) {
        cnt[i] += cnt[i-1];
    }
    sort(st2,st2+2*n,cmp2);
    for (int i=0; i<2*n; i++) {
        if(st2[i].p == 0){
            num[st2[i].i] = st2[i].num = cnt[dp[st2[i].i] - 1] + (pcnt[dp[st2[i].i]]++);
        }
        else{
            st2[i].num = num[st2[i].i];
        }
    }
    sort(st2,st2+2*n,cmp3);
    idx.init(n);
    for (int i=0; i<2*n; i++) {
        if(st2[i].p == 0){
            if(st2[i].dp == 1) rcnt[st2[i].i] = 1;
            else rcnt[st2[i].i] = idx.q(cnt[st2[i].dp-2], cnt[st2[i].dp-1]-1);
        }
        else{
            idx.ins(st2[i].num,rcnt[st2[i].i]);
        }
    }
    int acnt = 0;
    for (int i=0; i<n; i++) {
        if(dp[i] == mcnt){
            acnt += rcnt[i];
            acnt %= 30013;
        }
    }
    printf("%d",acnt);
}

Compilation message

trapezoid.cpp: In function 'void input()':
trapezoid.cpp:94:33: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i] = {a[i],c[i],0,i};
                                 ^
trapezoid.cpp:94:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i] = {a[i],c[i],0,i};
                 ^
trapezoid.cpp:95:35: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i+1] = {b[i],d[i],1,i};
                                   ^
trapezoid.cpp:95:19: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[2*i+1] = {b[i],d[i],1,i};
                   ^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:105:63: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
                                                               ^
trapezoid.cpp:105:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
                    ^
trapezoid.cpp:109:63: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
                                                               ^
trapezoid.cpp:109:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
             st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
                    ^
trapezoid.cpp: In function 'void input()':
trapezoid.cpp:78:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:81:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
                                                     ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12744 KB Output is correct
2 Correct 0 ms 12744 KB Output is correct
3 Partially correct 0 ms 12744 KB Partially correct
4 Correct 0 ms 12744 KB Output is correct
5 Partially correct 3 ms 12744 KB Partially correct
6 Partially correct 6 ms 12904 KB Partially correct
7 Correct 6 ms 12904 KB Output is correct
8 Partially correct 9 ms 12904 KB Partially correct
9 Partially correct 19 ms 13036 KB Partially correct
10 Correct 39 ms 13424 KB Output is correct
11 Partially correct 56 ms 13424 KB Partially correct
12 Partially correct 129 ms 14196 KB Partially correct
13 Partially correct 146 ms 14196 KB Partially correct
14 Partially correct 173 ms 15476 KB Partially correct
15 Partially correct 203 ms 15476 KB Partially correct
16 Runtime error 186 ms 15476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 213 ms 15476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 176 ms 15476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 229 ms 15476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 239 ms 15476 KB Execution killed with signal 11 (could be triggered by violating memory limits)