oj.uz

답안 #680812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680812 2023-01-11T20:22:12 Z stevancv 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 136 ms 43280 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());
    v.erase(unique(v.begin(), v.end()), 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 10 ms 14676 KB Execution killed with signal 11
2 Runtime error 12 ms 14676 KB Execution killed with signal 11
3 Runtime error 11 ms 14932 KB Execution killed with signal 6
4 Runtime error 13 ms 15060 KB Execution killed with signal 6
5 Runtime error 14 ms 15220 KB Execution killed with signal 11
6 Runtime error 13 ms 15656 KB Execution killed with signal 11
7 Runtime error 14 ms 15812 KB Execution killed with signal 11
8 Runtime error 15 ms 16212 KB Execution killed with signal 6
9 Runtime error 24 ms 17544 KB Execution killed with signal 11
10 Runtime error 28 ms 20476 KB Execution killed with signal 11
11 Runtime error 33 ms 21796 KB Execution killed with signal 11
12 Runtime error 59 ms 29076 KB Execution killed with signal 11
13 Runtime error 69 ms 31892 KB Execution killed with signal 11
14 Runtime error 82 ms 34744 KB Execution killed with signal 11
15 Runtime error 87 ms 36132 KB Execution killed with signal 11
16 Runtime error 100 ms 37640 KB Execution killed with signal 11
17 Runtime error 116 ms 39060 KB Execution killed with signal 11
18 Runtime error 108 ms 40444 KB Execution killed with signal 11
19 Runtime error 106 ms 41872 KB Execution killed with signal 11
20 Runtime error 136 ms 43280 KB Execution killed with signal 11