oj.uz

Submission #79790

# Submission time Handle Problem Language Result Execution time Memory
79790 2018-10-16T13:01:28 Z aquablitz11 trapezoid (balkan11_trapezoid) C++14
42 / 100
 500 ms 66560 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);
    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

# Verdict Execution time Memory 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