oj.uz

Submission #12033

# Submission time Handle Problem Language Result Execution time Memory
12033 2014-12-19T05:05:39 Z gs14004 trapezoid (balkan11_trapezoid) C++
50 / 100
 500 ms 7812 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int a[100005], b[100005], c[100005], d[100005];
vector<int> vu, vd;
int dp[100005], cnt[100005];

struct seg{int a,b,c,d;}st[100005];
bool cmp(seg a, seg b){return a.a < b.a;}

int main(){
    scanf("%d",&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[i] = {a[i],b[i],c[i],d[i]};
    }
    sort(st,st+n,cmp);
    for (int i=0; i<n; i++) {
        a[i] = st[i].a;
        b[i] = st[i].b;
        c[i] = st[i].c;
        d[i] = st[i].d;
    }
    for (int i=0; i<n; i++) {
        dp[i] = 1;
        for (int j=0; j<i; j++) {
            if(b[j] < a[i] && d[j] < c[i]){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        for (int j=0; j<i; j++) {
            if(dp[j] + 1 == dp[i] && b[j] < a[i] && d[j] < c[i]){
                cnt[i] += cnt[j];
                cnt[i] %= 30013;
            }
        }
        if(dp[i] == 1) cnt[i] = 1;
    }
    int mcnt = *max_element(dp,dp+n);
    int rcnt = 0;
    for (int i=0; i<n; i++) {
        if(dp[i] == mcnt){
            rcnt += cnt[i];
            rcnt %= 30013;
        }
    }
    printf("%d %d",mcnt,rcnt);
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:30:37: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[i] = {a[i],b[i],c[i],d[i]};
                                     ^
trapezoid.cpp:30:15: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         st[i] = {a[i],b[i],c[i],d[i]};
               ^
trapezoid.cpp:15:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:17: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]);
                                                     ^

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5080 KB Output is correct
2 Correct 0 ms 5080 KB Output is correct
3 Correct 0 ms 5080 KB Output is correct
4 Correct 0 ms 5080 KB Output is correct
5 Correct 6 ms 5080 KB Output is correct
6 Correct 13 ms 5240 KB Output is correct
7 Correct 19 ms 5240 KB Output is correct
8 Correct 59 ms 5240 KB Output is correct
9 Correct 183 ms 5372 KB Output is correct
10 Correct 403 ms 5760 KB Output is correct
11 Execution timed out 500 ms 5760 KB Execution timed out
12 Execution timed out 500 ms 6532 KB Execution timed out
13 Execution timed out 500 ms 6532 KB Execution timed out
14 Execution timed out 500 ms 7812 KB Execution timed out
15 Execution timed out 500 ms 7812 KB Execution timed out
16 Execution timed out 500 ms 7812 KB Execution timed out
17 Execution timed out 500 ms 7812 KB Execution timed out
18 Execution timed out 500 ms 7812 KB Execution timed out
19 Execution timed out 500 ms 7812 KB Execution timed out
20 Execution timed out 500 ms 7812 KB Execution timed out