Submission #31931

#	Time	Username	Problem	Language	Result	Execution time	Memory
31931		Extazy	trapezoid (balkan11_trapezoid)	C++14	20 / 100	500 ms	9480 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;

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 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);
    }
    
    printf("%d 1\n", ans);

    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:45:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:47: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: 20 / 100