oj.uz

Submission #31930

# Submission time Handle Problem Language Result Execution time Memory
31930 2017-09-16T09:00:40 Z Extazy trapezoid (balkan11_trapezoid) C++14
16 / 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;
    }
};

struct hash_pair {
    long long operator () (const pair < int, int > &a) const {
        return a.first*1000003ll+a.second;
    }
};

int n,sz,p[N];
map < int, int > code;
unordered_map < pair < int, int >, int, hash_pair > it;
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[make_pair(i^KEY,j^KEY)]=max(it[make_pair(i^KEY,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[make_pair(i^KEY,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:70:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:72: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
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 4748 KB Partially correct
2 Partially correct 0 ms 4880 KB Partially correct
3 Partially correct 3 ms 5512 KB Partially correct
4 Partially correct 6 ms 6180 KB Partially correct
5 Partially correct 23 ms 10224 KB Partially correct
6 Partially correct 56 ms 14128 KB Partially correct
7 Partially correct 46 ms 11428 KB Partially correct
8 Partially correct 169 ms 23428 KB Partially correct
9 Execution timed out 500 ms 43132 KB Execution timed out
10 Execution timed out 500 ms 48840 KB Execution timed out
11 Execution timed out 500 ms 65536 KB Execution timed out
12 Runtime error 16 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 26 ms 4748 KB Execution killed because of forbidden syscall futex (202)
14 Runtime error 13 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 16 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 19 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 19 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 16 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 19 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 9 ms 4748 KB Execution killed with signal 11 (could be triggered by violating memory limits)