답안 #79791 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79791	2018-10-16T13:02:55 Z	aquablitz11	사다리꼴 (balkan11_trapezoid)	C++14	90 / 100	500 ms	48264 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)%30013);
    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
90.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12668 KB	Output is correct
2	Correct	13 ms	12672 KB	Output is correct
3	Correct	15 ms	13008 KB	Output is correct
4	Correct	16 ms	13036 KB	Output is correct
5	Correct	19 ms	13484 KB	Output is correct
6	Correct	24 ms	13944 KB	Output is correct
7	Correct	23 ms	14244 KB	Output is correct
8	Correct	31 ms	14684 KB	Output is correct
9	Correct	52 ms	16628 KB	Output is correct
10	Correct	83 ms	20532 KB	Output is correct
11	Correct	118 ms	22084 KB	Output is correct
12	Correct	253 ms	30708 KB	Output is correct
13	Correct	343 ms	33328 KB	Output is correct
14	Correct	393 ms	38828 KB	Output is correct
15	Correct	490 ms	40620 KB	Output is correct
16	Execution timed out	519 ms	42412 KB	Time limit exceeded
17	Correct	498 ms	43816 KB	Output is correct
18	Correct	426 ms	45368 KB	Output is correct
19	Correct	481 ms	46652 KB	Output is correct
20	Execution timed out	569 ms	48264 KB	Time limit exceeded

답안 #79791

Compilation message

Subtask #1 90.0 / 100.0

Subtask #1
90.0 / 100.0