oj.uz

Submission #31931

# Submission time Handle Problem Language Result Execution time Memory
31931 2017-09-16T09:05:10 Z Extazy trapezoid (balkan11_trapezoid) C++14
20 / 100
 500 ms 9480 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;

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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 5256 KB Partially correct
2 Partially correct 0 ms 5256 KB Partially correct
3 Partially correct 0 ms 5256 KB Partially correct
4 Partially correct 0 ms 5388 KB Partially correct
5 Partially correct 6 ms 5520 KB Partially correct
6 Partially correct 16 ms 5784 KB Partially correct
7 Partially correct 19 ms 5652 KB Partially correct
8 Partially correct 29 ms 5916 KB Partially correct
9 Partially correct 153 ms 6972 KB Partially correct
10 Partially correct 366 ms 7104 KB Partially correct
11 Execution timed out 500 ms 9480 KB Execution timed out
12 Runtime error 23 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 26 ms 5256 KB Execution killed because of forbidden syscall futex (202)
14 Runtime error 23 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 16 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 19 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 16 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 23 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 23 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 16 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)