oj.uz

Submission #935043

# Submission time Handle Problem Language Result Execution time Memory
935043 2024-02-28T13:03:33 Z sleepntsheep trapezoid (balkan11_trapezoid) C++17
0 / 100
 500 ms 65540 KB 
#include <iostream>
#include <numeric>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500005

struct A
{
    int hi = -1, freq = 0;

    friend A operator+(A a, A b)
    {
        if (b.hi > a.hi) return b;
        if (a.hi > b.hi) return a;
        return A{a.hi, (a.freq + b.freq) % 30013};
    }

    void operator+=(A a) { *this = *this + a; }
};

int n;
A t[N+5<<1];
array<int, 4> a[N];

int stsz = N;
void upd(int p, A k)
{
    for (t[p += N] += k; p >>= 1;) t[p] = t[p<<1] + t[p<<1|1];
}

A qry(int l, int r)
{
    A z{-1,0};
    for (l += N, r += N; l < r; l >>= 1, r >>= 1)
    {
        if(l&1) z += t[l++];
        if(r&1) z = t[--r] + z;
    }
    return z;
}

vector<int> cx;
A dp[N];
basic_string<int> at_a[N], at_b[N];

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) for (auto &x : a[i]) cin >> x, cx.push_back(x);

    int oo = 1e9+1;
    a[n++] = {oo, oo, oo, oo};
    cx.push_back(-1);
    cx.push_back(oo);

    sort(cx.begin(), cx.end());
    cx.resize(unique(cx.begin(), cx.end()) - cx.begin());

    sort(a, a+n);

    for (int i = 0; i < n; ++i)
        at_a[a[i][0]].push_back(i),
        at_b[a[i][1]].push_back(i);

    upd(0, A{0, 1});

    for (int x = 0; x < N; ++x)
    {
        for (auto i : at_a[x])
        {
            auto [a, b, c, d] = ::a[i];
            dp[i] = qry(0, c);
            dp[i].hi++;
        }

        for (auto i : at_b[x]) upd(a[i][3], dp[i]);
    }

    cout << dp[n-1].hi-1 << ' ' << dp[n-1].freq;

    return 0;
}

Compilation message

trapezoid.cpp:35:6: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   35 | A t[N+5<<1];
      |      ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2251 ms 65536 KB Time limit exceeded
2 Execution timed out 2138 ms 65536 KB Time limit exceeded
3 Execution timed out 2321 ms 65536 KB Time limit exceeded
4 Execution timed out 2168 ms 65536 KB Time limit exceeded
5 Runtime error 153 ms 65536 KB Execution killed with signal 9
6 Runtime error 161 ms 65536 KB Execution killed with signal 9
7 Runtime error 175 ms 65536 KB Execution killed with signal 9
8 Runtime error 174 ms 65536 KB Execution killed with signal 9
9 Runtime error 171 ms 65536 KB Execution killed with signal 9
10 Runtime error 179 ms 65536 KB Execution killed with signal 9
11 Runtime error 158 ms 65536 KB Execution killed with signal 9
12 Runtime error 180 ms 65536 KB Execution killed with signal 9
13 Runtime error 202 ms 65540 KB Execution killed with signal 9
14 Runtime error 183 ms 65536 KB Execution killed with signal 9
15 Runtime error 193 ms 65536 KB Execution killed with signal 9
16 Runtime error 213 ms 65540 KB Execution killed with signal 9
17 Runtime error 222 ms 65540 KB Execution killed with signal 9
18 Runtime error 214 ms 65536 KB Execution killed with signal 9
19 Runtime error 205 ms 65536 KB Execution killed with signal 9
20 Runtime error 205 ms 65540 KB Execution killed with signal 9