oj.uz

Submission #31934

# Submission time Handle Problem Language Result Execution time Memory
31934 2017-09-16T09:10:05 Z Extazy trapezoid (balkan11_trapezoid) C++14
18 / 100
 500 ms 65536 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 KEY = 3293283;
 
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;
unordered_map < int, int > it[N*4];
int all;
int ans;
trapezoid a[N];
 
void update(int x, int y, int value) {
    for(int i=x;i<=all;i+=i&(-i)) {
        for(int j=y;j<=all;j+=j&(-j)) {
            it[i][j^KEY]=max(it[i][j^KEY],value);
        }
    }
}
 
int query(int x, int y) {
    int ans=0;
    for(int i=x;i>=1;i-=i&(-i)) {
        for(int j=y;j>=1;j-=j&(-j)) {
            ans=max(ans,it[i][j^KEY]);
        }
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,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+query(a[i].ac.first-1,a[i].ac.second-1);
        ans=max(ans,curr);
        update(a[i].bd.first,a[i].bd.second,curr);
    }
 
    printf("%d 1\n", ans);
 
    return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 34956 KB Partially correct
2 Partially correct 9 ms 34956 KB Partially correct
3 Partially correct 16 ms 35616 KB Partially correct
4 Partially correct 16 ms 36012 KB Partially correct
5 Partially correct 36 ms 39048 KB Partially correct
6 Partially correct 63 ms 41192 KB Partially correct
7 Partially correct 56 ms 40376 KB Partially correct
8 Partially correct 119 ms 47268 KB Partially correct
9 Partially correct 329 ms 61888 KB Partially correct
10 Memory limit exceeded 259 ms 65536 KB Memory limit exceeded
11 Memory limit exceeded 283 ms 65536 KB Memory limit exceeded
12 Memory limit exceeded 416 ms 65536 KB Memory limit exceeded
13 Memory limit exceeded 443 ms 65536 KB Memory limit exceeded
14 Memory limit exceeded 486 ms 65536 KB Memory limit exceeded
15 Execution timed out 500 ms 65536 KB Execution timed out
16 Execution timed out 500 ms 65536 KB Execution timed out
17 Execution timed out 500 ms 65536 KB Execution timed out
18 Memory limit exceeded 419 ms 65536 KB Memory limit exceeded
19 Execution timed out 500 ms 65536 KB Execution timed out
20 Execution timed out 500 ms 65536 KB Execution timed out