oj.uz

Submission #31932

# Submission time Handle Problem Language Result Execution time Memory
31932 2017-09-16T09:08:14 Z Extazy trapezoid (balkan11_trapezoid) C++14
45 / 100
 500 ms 9992 KB 
#include <bits/stdc++.h>
#define endl '\n'

#define left aklhgjqghkqkj
#define right ajklvhajkvhajk
#define prev aioghajga
#define next ioyhjhfajasj
#define y0 iuadoghasdgj
#define y1 taklahgjkla
#define remainder pogjuakllhga
#define pow pajklgaklha
#define pow10 iopuioadjlgkah
#define div aljghajkghak
#define distance gkuftgjasgfjh
#define uppercase ifyhasjkhakjfas
#define tm aogqjgklqjgqklgjqlkq

//#define floor hjakjhaja
//#define time ashjlahjka
//#define double_t double

using namespace std;

const int N = 1<<17;
const int MOD = 30013;

struct trapezoid {
    pair < int, int > ac, bd;
    bool operator <(const trapezoid &a) const {
        return bd<a.bd;
    }
};

int n,sz,p[N];
map < int, int > code;
int all;
int ans;
trapezoid a[N];
int anscnt;
int cnt[N],dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j,x,y,z,w;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        a[i].ac=make_pair(x,z);
        a[i].bd=make_pair(y,w);
        p[++sz]=a[i].ac.first;
        p[++sz]=a[i].ac.second;
        p[++sz]=a[i].bd.first;
        p[++sz]=a[i].bd.second;
    }

    sort(p+1,p+1+sz);
    code[p[1]]=1;
    for(i=2;i<=sz;i++) if(p[i]!=p[i-1]) {
        code[p[i]]=code[p[i-1]]+1;
    }
    all=code[p[sz]];

    for(i=1;i<=n;i++) {
        a[i].ac=make_pair(code[a[i].ac.first],code[a[i].ac.second]);
        a[i].bd=make_pair(code[a[i].bd.first],code[a[i].bd.second]);
    }

    sort(a+1,a+1+n);
    for(i=1;i<=n;i++) {
        int curr=1;
        for(j=i-1;j>=1;j--) {
            if(a[j].bd.first<a[i].ac.first && a[j].bd.second<a[i].ac.second) {
                curr=max(curr,1+dp[j]);
            }
        }
        dp[i]=curr;
        ans=max(ans,curr);
        if(curr==1) {
            cnt[i]=1;
        }
        else {
            for(j=i-1;j>=1;j--) {
                if(a[j].bd.first<a[i].ac.first && a[j].bd.second<a[i].ac.second) {
                    if(dp[j]+1==dp[i]) {
                        cnt[i]=(cnt[i]+cnt[j])%MOD;
                    }
                }
            }
        }
    }

    for(i=1;i<=n;i++) {
        if(dp[i]==ans) {
            anscnt=(anscnt+cnt[i])%MOD;
        }
    }
    
    printf("%d %d\n", ans, anscnt);

    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:47:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:49:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &x, &y, &z, &w);
                                             ^

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5768 KB Output is correct
2 Correct 0 ms 5768 KB Output is correct
3 Correct 0 ms 5768 KB Output is correct
4 Correct 3 ms 5900 KB Output is correct
5 Correct 9 ms 6032 KB Output is correct
6 Correct 23 ms 6296 KB Output is correct
7 Correct 29 ms 6164 KB Output is correct
8 Correct 46 ms 6428 KB Output is correct
9 Correct 256 ms 7484 KB Output is correct
10 Execution timed out 500 ms 7616 KB Execution timed out
11 Execution timed out 500 ms 9992 KB Execution timed out
12 Runtime error 16 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 29 ms 5768 KB Execution killed because of forbidden syscall futex (202)
14 Runtime error 13 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 16 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 16 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 23 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 16 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 16 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 6 ms 5768 KB Execution killed with signal 11 (could be triggered by violating memory limits)