Submission #31933

#	Time	Username	Problem	Language	Result	Execution time	Memory
31933		Extazy	trapezoid (balkan11_trapezoid)	C++14	45 / 100	500 ms	22880 KiB

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 (stderr)

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 / 100