oj.uz

답안 #79803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79803 2018-10-16T13:36:00 Z aquablitz11 사다리꼴 (balkan11_trapezoid) C++14
85 / 100
 500 ms 46820 KB 
#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];
 
struct data {
    vector<int> key;
    vector<pii> val;
    data() {
        key.clear();
        val.clear();
    }
    data(int x) {
        key.push_back(x);
        val = vector<pii>(2, pii(0, 0));
    }
} seg[N<<1];
vector<pii> coord;
 
void build(int p=1, int b=0, int e=n-1) {
    if (b == e) {
        seg[p] = data(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].key), all(seg[p<<1|1].key), back_inserter(seg[p].key));
    seg[p].val.resize(e-b+2, pii(0, 0));
}
 
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].key), y)-seg[p].key.begin()+1;
        pii ans(0, 0);
        for (; i <= seg[p].key.size(); i += i&-i)
            ans = comb(ans, seg[p].val[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);
}
 
inline void updateft(int p, int i, pii v) {
    for (; i > 0; i -= i&-i)
        seg[p].val[i] = comb(seg[p].val[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].key), y)-seg[p].key.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:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; i <= seg[p].key.size(); i += i&-i)
                ~~^~~~~~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:92: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
85.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12664 KB Output is correct
2 Correct 14 ms 12668 KB Output is correct
3 Correct 15 ms 13000 KB Output is correct
4 Correct 17 ms 13028 KB Output is correct
5 Correct 19 ms 13360 KB Output is correct
6 Correct 22 ms 13660 KB Output is correct
7 Correct 24 ms 13932 KB Output is correct
8 Correct 31 ms 14424 KB Output is correct
9 Correct 53 ms 16108 KB Output is correct
10 Correct 87 ms 19448 KB Output is correct
11 Correct 128 ms 20984 KB Output is correct
12 Correct 253 ms 29288 KB Output is correct
13 Correct 358 ms 32116 KB Output is correct
14 Correct 411 ms 37360 KB Output is correct
15 Correct 475 ms 39288 KB Output is correct
16 Execution timed out 508 ms 40816 KB Time limit exceeded
17 Execution timed out 505 ms 42540 KB Time limit exceeded
18 Correct 404 ms 43880 KB Output is correct
19 Correct 490 ms 45412 KB Output is correct
20 Execution timed out 567 ms 46820 KB Time limit exceeded