oj.uz

답안 #31936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31936 2017-09-16T09:11:20 Z Extazy 사다리꼴 (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;
    }
};
 
struct hash_pair {
    long long operator () (const pair < int, int > &a) const {
        return a.first*1000003ll+a.second;
    }
};
 
int n,sz,p[N*4];
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
18.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 6284 KB Partially correct
2 Partially correct 0 ms 6416 KB Partially correct
3 Partially correct 3 ms 7048 KB Partially correct
4 Partially correct 6 ms 7716 KB Partially correct
5 Partially correct 29 ms 11760 KB Partially correct
6 Partially correct 73 ms 15664 KB Partially correct
7 Partially correct 43 ms 12964 KB Partially correct
8 Partially correct 169 ms 24964 KB Partially correct
9 Partially correct 483 ms 44668 KB Partially correct
10 Execution timed out 500 ms 50376 KB Execution timed out
11 Execution timed out 500 ms 65536 KB Execution timed out
12 Execution timed out 500 ms 65536 KB Execution timed out
13 Execution timed out 500 ms 62996 KB Execution timed out
14 Execution timed out 500 ms 63952 KB Execution timed out
15 Execution timed out 500 ms 63032 KB Execution timed out
16 Execution timed out 500 ms 58840 KB Execution timed out
17 Execution timed out 500 ms 61268 KB Execution timed out
18 Execution timed out 500 ms 65536 KB Execution timed out
19 Execution timed out 500 ms 62740 KB Execution timed out
20 Execution timed out 500 ms 58820 KB Execution timed out