Submission #31933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31933	2017-09-16T09:09:07 Z	Extazy	trapezoid (balkan11_trapezoid)	C++14	45 / 100	500 ms	22880 KB

trapezoid

#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*4];
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	7304 KB	Output is correct
2	Correct	0 ms	7304 KB	Output is correct
3	Correct	0 ms	7304 KB	Output is correct
4	Correct	3 ms	7436 KB	Output is correct
5	Correct	9 ms	7568 KB	Output is correct
6	Correct	23 ms	7832 KB	Output is correct
7	Correct	29 ms	7700 KB	Output is correct
8	Correct	49 ms	7964 KB	Output is correct
9	Correct	249 ms	9020 KB	Output is correct
10	Execution timed out	500 ms	9152 KB	Execution timed out
11	Execution timed out	500 ms	11528 KB	Execution timed out
12	Execution timed out	500 ms	16148 KB	Execution timed out
13	Execution timed out	500 ms	17468 KB	Execution timed out
14	Execution timed out	500 ms	19844 KB	Execution timed out
15	Execution timed out	500 ms	18260 KB	Execution timed out
16	Execution timed out	500 ms	18920 KB	Execution timed out
17	Execution timed out	500 ms	21428 KB	Execution timed out
18	Execution timed out	500 ms	15752 KB	Execution timed out
19	Execution timed out	500 ms	22616 KB	Execution timed out
20	Execution timed out	500 ms	22880 KB	Execution timed out