oj.uz

답안 #680815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680815 2023-01-11T20:27:37 Z stevancv 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 111 ms 43328 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int mod = 30013;
int Add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}
struct Node {
    int x, y;
    Node() {
        x = y = 0;
    }
    Node(int a, int b) {
        x = a; y = b;
    }
};
Node Merge(Node a, Node b) {
    Node c;
    if (a.x > b.x) c = a;
    else if (a.x < b.x) c = b;
    else c = Node(a.x, Add(a.y, b.y));
}
Node st[8 * N];
void Set(int node, int l, int r, int p, int x, int y) {
    if (l == r) {
        st[node] = Node(x, y);
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid) Set(2 * node, l, mid, p, x, y);
    else Set(2 * node + 1, mid + 1, r, p, x, y);
    st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
Node Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return Node();
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return Merge(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
Node ans[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    vector<int> a(n), b(n), c(n), d(n);
    vector<array<int, 3>> all;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        all.push_back({a[i], i, 0});
        all.push_back({b[i], i, 1});
        v.push_back(c[i]); v.push_back(d[i]);
    }
    sort(v.begin(), v.end());
    sort(all.begin(), all.end());
    map<int, int> mp;
    int x = 0;
    for (int i : v) mp[i] = x++;
    for (auto u : all) {
        if (u[2] == 0) {
            ans[u[1]] = Get(1, 0, x - 1, 0, mp[c[u[1]]]);
            ans[u[1]].x += 1;
            if (ans[u[1]].x == 1) ans[u[1]].y += 1;
        }
        else Set(1, 0, x - 1, mp[d[u[1]]], ans[u[1]].x, ans[u[1]].y);
    }
    int mx = 0;
    for (int i = 0; i < n; i++) smax(mx, ans[i].x);
    int sol = 0;
    for (int i = 0; i < n; i++) if (ans[i].x == mx) sol = Add(sol, ans[i].y);
    cout << mx << sp << sol << en;
    return 0;
}

Compilation message

trapezoid.cpp: In function 'Node Merge(Node, Node)':
trapezoid.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
   30 | }
      | ^
trapezoid.cpp: In function 'void Set(int, int, int, int, int, int)':
trapezoid.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
trapezoid.cpp: In function 'Node Get(int, int, int, int, int)':
trapezoid.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 14664 KB Execution killed with signal 11
2 Runtime error 11 ms 14728 KB Execution killed with signal 11
3 Runtime error 10 ms 14804 KB Execution killed with signal 6
4 Runtime error 11 ms 15036 KB Execution killed with signal 6
5 Runtime error 11 ms 15252 KB Execution killed with signal 11
6 Runtime error 16 ms 15628 KB Execution killed with signal 11
7 Runtime error 13 ms 15780 KB Execution killed with signal 11
8 Runtime error 14 ms 16212 KB Execution killed with signal 6
9 Runtime error 18 ms 17572 KB Execution killed with signal 11
10 Runtime error 28 ms 20460 KB Execution killed with signal 11
11 Runtime error 34 ms 21940 KB Execution killed with signal 11
12 Runtime error 59 ms 29024 KB Execution killed with signal 11
13 Runtime error 71 ms 31824 KB Execution killed with signal 11
14 Runtime error 84 ms 34740 KB Execution killed with signal 11
15 Runtime error 92 ms 36180 KB Execution killed with signal 11
16 Runtime error 90 ms 37672 KB Execution killed with signal 11
17 Runtime error 96 ms 39048 KB Execution killed with signal 11
18 Runtime error 101 ms 40404 KB Execution killed with signal 11
19 Runtime error 107 ms 41876 KB Execution killed with signal 11
20 Runtime error 111 ms 43328 KB Execution killed with signal 11