제출 #31934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31934		Extazy	사다리꼴 (balkan11_trapezoid)	C++14	18 / 100	500 ms	65536 KiB

trapezoid

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 100