oj.uz

Submission #874335

# Submission time Handle Problem Language Result Execution time Memory
874335 2023-11-16T17:05:17 Z Macker trapezoid (balkan11_trapezoid) C++17
46 / 100
 183 ms 13780 KB 
#include <iostream> // #include <fstream>
#include <vector>
#include <list>
#include <algorithm>
#include <math.h>
#include <tuple>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <array>
#include <climits>
#include <cassert>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

//ifstream cin("optmilk.in");
//ofstream cout("optmilk.out");

vector<pair<int, int>> st;
int len = 1;
int mod = 30013;

vector<int> xs;
int cx(int x) {
    return lower_bound(all(xs), x) - xs.begin();
}

pair<int, int> query(int f, int t, int i = 1, int s = 0, int e = len) {
    if (f >= e || t <= s) return { -1, -1 };
    if (f <= s && e <= t) return st[i];

    pair<int, int> a = query(f, t, i * 2, s, (s + e) / 2);
    pair<int, int> b = query(f, t, i * 2 + 1, (s + e) / 2, e);
    if (a.first > b.first) return a;
    if (a.first < b.first) return b;
    if (a.first == b.first) return { a.first, a.second + b.second };
}

void add(int idx, int val, int cnt, int i = 1, int s = 0, int e = len) {
    if (s > idx || e <= idx) return;
    if (s == idx && s == e - 1) {
        if (st[i].first == val) st[i].second += cnt;
        if (st[i].first < val) st[i] = { val, cnt };
        return;
    }
    add(idx, val, cnt, i * 2, s, (s + e) / 2);
    add(idx, val, cnt, i * 2 + 1, (s + e) / 2, e);
    if (st[i * 2].first == st[i * 2 + 1].first) st[i] = { st[i * 2].first, st[i * 2].second + st[i * 2 + 1].second };
    if (st[i * 2].first > st[i * 2 + 1].first) st[i] = st[i * 2];
    if (st[i * 2].first < st[i * 2 + 1].first) st[i] = st[i * 2 + 1];
}

int main()
{
    int n; cin >> n;
    vector<array<int, 5>> ev; // y, t - 0add/1query, x1, -1/(val, val)
    for (int i = 0; i < n; i++) {
        int y, yy, x, xx; cin >> x >> xx >> y >> yy;
        ev.push_back({ y, 1, x, yy, -1 });
        ev.push_back({ yy, 0, xx, -1, -1 });
        xs.push_back(x);
        xs.push_back(xx);
    }
    sort(all(ev));
    sort(all(xs));
    while (len < xs.size()) len *= 2;
    st.resize(len * 2, { 0, 0 });
    
    for (int i = 0; i < ev.size(); i++) {
        int y = ev[i][0], t = ev[i][1], x = ev[i][2];
        if (t == 1) {
            pair<int, int> val = query(0, cx(x) + 1);
            if (val.first == 0) val.second = 1;
            array<int, 5>& tmp = *lower_bound(all(ev), array<int, 5>({ev[i][3], -1, -1, -1, -1 }));
            tmp[3] = val.first + 1; tmp[4] = val.second;
        }
        else {
            int ans = ev[i][3], cnt = ev[i][4];
            add(cx(x), ans, cnt);
        }
    }

    cout << st[1].first << " " << st[1].second << endl;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     while (len < xs.size()) len *= 2;
      |            ~~~~^~~~~~~~~~~
trapezoid.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 5> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < ev.size(); i++) {
      |                     ~~^~~~~~~~~~~
trapezoid.cpp:74:13: warning: unused variable 'y' [-Wunused-variable]
   74 |         int y = ev[i][0], t = ev[i][1], x = ev[i][2];
      |             ^
trapezoid.cpp: In function 'std::pair<int, int> query(int, int, int, int, int)':
trapezoid.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 3 ms 600 KB Partially correct
6 Partially correct 5 ms 860 KB Partially correct
7 Partially correct 6 ms 860 KB Partially correct
8 Partially correct 8 ms 952 KB Partially correct
9 Partially correct 17 ms 1752 KB Partially correct
10 Partially correct 41 ms 3132 KB Partially correct
11 Partially correct 42 ms 3556 KB Partially correct
12 Partially correct 90 ms 6700 KB Partially correct
13 Partially correct 105 ms 7200 KB Partially correct
14 Partially correct 126 ms 12384 KB Partially correct
15 Partially correct 136 ms 12884 KB Partially correct
16 Partially correct 158 ms 12344 KB Partially correct
17 Partially correct 157 ms 13168 KB Partially correct
18 Partially correct 155 ms 12784 KB Partially correct
19 Partially correct 165 ms 13404 KB Partially correct
20 Partially correct 183 ms 13780 KB Partially correct