oj.uz

Submission #31929

# Submission time Handle Problem Language Result Execution time Memory
31929 2017-09-16T08:58:00 Z Extazy trapezoid (balkan11_trapezoid) C++14
18 / 100
 276 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];
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 33420 KB Partially correct
2 Partially correct 9 ms 33420 KB Partially correct
3 Partially correct 19 ms 34080 KB Partially correct
4 Partially correct 16 ms 34476 KB Partially correct
5 Partially correct 39 ms 37512 KB Partially correct
6 Partially correct 46 ms 39656 KB Partially correct
7 Partially correct 46 ms 38840 KB Partially correct
8 Partially correct 129 ms 45732 KB Partially correct
9 Partially correct 276 ms 60352 KB Partially correct
10 Memory limit exceeded 263 ms 65536 KB Memory limit exceeded
11 Memory limit exceeded 269 ms 65536 KB Memory limit exceeded
12 Runtime error 26 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 49 ms 33420 KB Execution killed because of forbidden syscall futex (202)
14 Runtime error 19 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 23 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 19 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 29 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 26 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 23 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 16 ms 33420 KB Execution killed with signal 11 (could be triggered by violating memory limits)