답안 #79790 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79790	2018-10-16T13:01:28 Z	aquablitz11	사다리꼴 (balkan11_trapezoid)	C++14	42 / 100	500 ms	66560 KB

trapezoid

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using piipii = pair<pii, pii>;
using pipii = pair<int, pii>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define F first
#define S second

pii comb(pii a, pii b) {
    if (a.F == b.F)
        return pii(a.F, a.S+b.S);
    else
        return max(a, b);
}

const int N = 1<<17;
int n;
piipii A[N];

vector<pii> coord;
vector<int> seg[N<<1];
vector<pii> val[N<<1];

void build(int p=1, int b=0, int e=n-1) {
    val[p].resize(e-b+2, pii(0, 0));
    if (b == e) {
        seg[p].push_back(A[coord[b].S].F.S);
        return;
    }
    int m = (b+e)/2;
    build(p<<1, b, m);
    build(p<<1|1, m+1, e);
    merge(all(seg[p<<1]), all(seg[p<<1|1]), back_inserter(seg[p]));
    //printf("position %d %d: ", b, e);
    //for (auto x : seg[p]) printf("%d ", x);
    //printf("\n");
}

pii query(int x, int y, int p=1, int b=0, int e=n-1) {
    int l = x, r = n-1;
    if (b > r || e < l)
        return pii(0, 0);
    if (b >= l && e <= r) {
        int i = lower_bound(all(seg[p]), y)-seg[p].begin()+1;
        pii ans(0, 0);
        for (; i <= seg[p].size(); i += i&-i)
            ans = comb(ans, val[p][i]);
        return ans;
    }
    int m = (b+e)/2;
    pii q1 = query(x, y, p<<1, b, m);
    pii q2 = query(x, y, p<<1|1, m+1, e);
    return comb(q1, q2);
}

void updateft(int p, int i, pii v) {
    for (; i > 0; i -= i&-i)
        val[p][i] = comb(val[p][i], v);
}

void update(int x, int y, pii v, int p=1, int b=0, int e=n-1) {
    if (b > x || e < x)
        return;
    updateft(p, lower_bound(all(seg[p]), y)-seg[p].begin()+1, v);
    if (b == e)
        return;
    int m = (b+e)/2;
    if (x <= m)
        update(x, y, v, p<<1, b, m);
    else
        update(x, y, v, p<<1|1, m+1, e);
}

int pos(int x) {
    return lower_bound(all(coord), pii(x, 0))-coord.begin();
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d%d%d", &A[i].F.F, &A[i].S.F, &A[i].F.S, &A[i].S.S);
    sort(A, A+n);
    for (int i = 0; i < n; ++i)
        coord.push_back(pii(A[i].F.F, i));
    sort(coord.begin(), coord.end());
    build();

    pii ans(0, 0);
    for (int i = n-1; i >= 0; --i) {
        int ul = A[i].F.F, dl = A[i].F.S;
        int ur = A[i].S.F, dr = A[i].S.S;
        pii best = query(pos(ur), dr);
        ++best.F;
        if (best == pii(1, 0))
            best.S = 1;
        ans = comb(ans, best);
        update(pos(ul), dl, best);
        //printf("ul=%d, dl=%d, update to %d %d\n", ul, dl, best.F, best.S);
    }
    printf("%d %d\n", ans.F, ans.S);

    return 0;
}

Compilation message

trapezoid.cpp: In function 'pii query(int, int, int, int, int)':
trapezoid.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; i <= seg[p].size(); i += i&-i)
                ~~^~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &A[i].F.F, &A[i].S.F, &A[i].F.S, &A[i].S.S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
42.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12660 KB	Output is correct
2	Correct	13 ms	12816 KB	Output is correct
3	Partially correct	19 ms	12928 KB	Partially correct
4	Partially correct	16 ms	13216 KB	Partially correct
5	Partially correct	19 ms	13396 KB	Partially correct
6	Partially correct	22 ms	13824 KB	Partially correct
7	Partially correct	24 ms	14236 KB	Partially correct
8	Partially correct	33 ms	14968 KB	Partially correct
9	Partially correct	58 ms	16676 KB	Partially correct
10	Partially correct	88 ms	20788 KB	Partially correct
11	Partially correct	114 ms	22768 KB	Partially correct
12	Partially correct	251 ms	32536 KB	Partially correct
13	Partially correct	308 ms	36988 KB	Partially correct
14	Partially correct	403 ms	44368 KB	Partially correct
15	Partially correct	462 ms	48092 KB	Partially correct
16	Execution timed out	503 ms	51880 KB	Time limit exceeded
17	Partially correct	500 ms	55804 KB	Partially correct
18	Partially correct	440 ms	59580 KB	Partially correct
19	Partially correct	462 ms	63596 KB	Partially correct
20	Execution timed out	563 ms	66560 KB	Time limit exceeded

답안 #79790

Compilation message

Subtask #1 42.0 / 100.0

Subtask #1
42.0 / 100.0