oj.uz

답안 #417703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417703 2021-06-04T07:15:04 Z MarcoMeijer 사다리꼴 (balkan11_trapezoid) C++14
40 / 100
 188 ms 37740 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<20);

int n;
int a[MX], b[MX], c[MX], d[MX];

// fenwick tree
int FT[MX];
void addFT(int i, int value) {
    for(i++; i<MX; i+=i&-i) FT[i] = max(FT[i],value);
}
int getFT(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans = max(ans, FT[i]);
    return ans;
}

// lis
int lis[MX];
vi atA[MX], atB[MX];

void program() {
    IN(n);
    RE(i,n) IN(a[i],b[i],c[i],d[i]);

    // coordinate compression
    vi difx;
    RE(i,n) difx.pb(a[i]), difx.pb(b[i]), difx.pb(c[i]), difx.pb(d[i]);
    sort(all(difx));
    RE(i,n) {
        a[i] = lower_bound(all(difx),a[i]) - difx.begin();
        b[i] = lower_bound(all(difx),b[i]) - difx.begin();
        c[i] = lower_bound(all(difx),c[i]) - difx.begin();
        d[i] = lower_bound(all(difx),d[i]) - difx.begin();
    }

    // getting lis
    RE(i,n) atA[a[i]].pb(i);
    RE(i,n) atB[b[i]].pb(i);
    RE(i,n*4) {
        FOR(j,atA[i])
            lis[j] = getFT(c[j]-1) + 1;
        FOR(j,atB[i])
            addFT(d[j], lis[j]);
    }

    int ans=0;
    RE(i,n) ans = max(ans,lis[i]);
    cout<<ans<<" 1"<<endl;
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 16 ms 23884 KB Partially correct
2 Partially correct 17 ms 23812 KB Partially correct
3 Partially correct 17 ms 23880 KB Partially correct
4 Partially correct 18 ms 23948 KB Partially correct
5 Partially correct 19 ms 24012 KB Partially correct
6 Partially correct 21 ms 24220 KB Partially correct
7 Partially correct 26 ms 24276 KB Partially correct
8 Partially correct 24 ms 24516 KB Partially correct
9 Partially correct 32 ms 25120 KB Partially correct
10 Partially correct 46 ms 26564 KB Partially correct
11 Partially correct 56 ms 27352 KB Partially correct
12 Partially correct 98 ms 30656 KB Partially correct
13 Partially correct 118 ms 32192 KB Partially correct
14 Partially correct 145 ms 33768 KB Partially correct
15 Partially correct 146 ms 34248 KB Partially correct
16 Partially correct 160 ms 35000 KB Partially correct
17 Partially correct 165 ms 35832 KB Partially correct
18 Partially correct 161 ms 36376 KB Partially correct
19 Partially correct 170 ms 36960 KB Partially correct
20 Partially correct 188 ms 37740 KB Partially correct