oj.uz

답안 #96263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96263 2019-02-07T15:17:01 Z updown1 사다리꼴 (balkan11_trapezoid) C++17
14 / 100
 500 ms 45432 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//500,000,000 operations
const int MAXN = 100000, MOD = 30013;
//Global Variables
int N, A[MAXN], B[MAXN], C[MAXN], D[MAXN], AB[2*MAXN], dpmax[MAXN], dpcnt[MAXN], treemax[8*MAXN+1], treecnt[8*MAXN+1];
map<int, int> ab, cd;
pair<int, int> CD[2*MAXN];


void update (int ind, int L, int R, int x, int i) {
    if (x < L || R < x) return;
    if (L == R) {
        treemax[ind] = dpmax[i];
        treecnt[ind] = dpcnt[i];
        return;
    }
    update(ind*2, L, (L+R)/2, x, i); update(ind*2+1, (L+R)/2+1, R, x, i);
    if (treemax[ind*2] == treemax[ind*2+1]) {
        treemax[ind] = treemax[ind*2];
        treecnt[ind] = treecnt[ind*2]+treecnt[ind*2+1];
    }
    else if (treemax[ind*2] > treemax[ind*2+1]) {
        treemax[ind] = treemax[ind*2];
        treecnt[ind] = treecnt[ind*2];
    }
    else {
        treemax[ind] = treemax[ind*2+1];
        treecnt[ind] = treecnt[ind*2+1];
    }
}
pair<int, int> query(int ind, int L, int R, int oL, int oR) { /// (max, cnt)
    if (oL <= L && R <= oR) return mp(treemax[ind], treecnt[ind]);
    if (R < oL || oR < L) return mp(0, 0);
    pair<int, int> i = query(ind*2, L, (L+R)/2, oL, oR), j = query(ind*2+1, (L+R)/2+1, R, oL, oR);
    if (i.a == j.a) return mp(i.a, i.b+j.b);
    if (i.a < j.a) return j;
    return i;
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    ffi {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        AB[2*i] = A[i], AB[2*i+1] = B[i];
        CD[2*i].a = C[i], CD[2*i+1].a = D[i];
        CD[2*i].b = CD[2*i+1].b = i;
    }
    /// coordinate compress. new coordinates: 1 : 2*N
    sort(AB, AB+2*N); sort(CD, CD+2*N);
    For (i, 1, 2*N+1) {
        ab[AB[i-1]] = i;
        cd[CD[i-1].a] = i;
    }
    ffi {
        A[i] = ab[A[i]]; B[i] = ab[B[i]]; C[i] = cd[C[i]]; D[i] = cd[D[i]];
        //w<< i c A[i] s B[i] s C[i] s D[i]<<e;
    }
    For (j, 0, 2*N) {
        int i = CD[j].b;
        if (dpmax[i] == 0) {
            /// we are at a C
            pair<int, int> get = query(1, 1, 2*N, 1, A[i]); /// (max, cnt)
            if (get.a == 0) get.b = 1;
            dpmax[i] = get.a+1;
            dpcnt[i] = get.b;
        }
        else {
            /// we are at a D
            update(1, 1, 2*N, B[i], i);
        }
    }
    int out1 = 0, out2 =0;
    ffi out1 = max(out1, dpmax[i]);
    ffi if (dpmax[i] == out1) out2 += dpcnt[i];
    w<< out1 s out2<<e;
}

Compilation message

trapezoid.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
14.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Incorrect 3 ms 532 KB Expected int32, but "10313130667392" found
4 Incorrect 4 ms 760 KB Expected int32, but "-8550276992825950208" found
5 Partially correct 6 ms 1272 KB Partially correct
6 Incorrect 9 ms 1784 KB Expected int32, but "-8629080777422869056" found
7 Incorrect 14 ms 2168 KB Expected int32, but "-3319866744691032064" found
8 Partially correct 17 ms 2680 KB Partially correct
9 Incorrect 36 ms 5292 KB Expected int32, but "2248786528710863832" found
10 Incorrect 76 ms 9884 KB Expected int32, but "-5022802232222890496" found
11 Incorrect 97 ms 11672 KB Expected int32, but "-1298419000938405298" found
12 Incorrect 223 ms 23032 KB Expected int32, but "9183932486774365824" found
13 Incorrect 252 ms 26744 KB Expected int32, but "-4195152448689438272" found
14 Incorrect 333 ms 34680 KB Expected int32, but "-3175106568905838848" found
15 Incorrect 363 ms 36472 KB Expected int32, but "-8026369531311511552" found
16 Incorrect 410 ms 38264 KB Expected int32, but "6233362917342126368" found
17 Incorrect 439 ms 40440 KB Expected int32, but "-7505826292837535760" found
18 Incorrect 389 ms 42088 KB Expected int32, but "-6197299359079266322" found
19 Incorrect 434 ms 42872 KB Expected int32, but "5619696618904563712" found
20 Execution timed out 520 ms 45432 KB Time limit exceeded