oj.uz

답안 #779785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779785 2023-07-11T20:11:37 Z chanhchuong123 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 99 ms 12736 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};

const int MAX = 100100;
int n;
vector<int> tmp[2];
#define ID(x, tmp) (upper_bound(all(tmp), x) - tmp.begin())

struct range {
    int a, b, c, d;

    range(int _a = 0, int _b = 0, int _c = 0, int _d = 0) {
        a = _a; b = _b; c = _c; d = _d;
    }

    bool operator< (const range &other) const {
        return a < other.a;
    }
};
range arr[MAX];

struct node {
    int len, cnt, pos;

    node(int _len = 0, int _cnt = 0, int _pos = 0) {
        len = _len; cnt = _cnt; pos = _pos;
    }
};
vector<node> add[MAX << 1];
pair<int, int> bit[MAX << 1];

pair<int, int> combine(const pair<int, int> &u, const pair<int, int> &v) {
    if (u.fi < v.fi) return v;
    if (u.fi > v.fi) return u;
    return make_pair(u.fi, (u.se + v.se) % 30013);
}

void update(int id, const pair<int, int> &value) {
    for (; id <= n * 2; id += id & -id)
        bit[id] = combine(bit[id], value);
}

pair<int, int> get(int id) {
    pair<int, int> res(0, 1);
    for (; id > 0; id -= id & -id)
        res = combine(res, bit[id]);
    ++res.fi; return res;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        arr[i] = range(a, b, c, d);
        tmp[0].push_back(a);
        tmp[0].push_back(b);
        tmp[1].push_back(c);
        tmp[1].push_back(d);
    }
    for (int i = 0; i < 2; ++i) {
        sort(all(tmp[i]));
        tmp[i].resize(unique(all(tmp[i])) - tmp[i].begin());
    }
    sort(arr + 1, arr + 1 + n);
    for (int i = 1; i <= n; ++i) {
        arr[i].a = ID(arr[i].a, tmp[0]);
        arr[i].b = ID(arr[i].b, tmp[0]);
        arr[i].c = ID(arr[i].c, tmp[1]);
        arr[i].d = ID(arr[i].d, tmp[1]);
    }
    int pos = 1;
    pair<int, int> ans(0, 1);
    for (int i = 1; i <= n; ++i) {
        while (pos <= arr[i].a) {
            for (node &x: add[pos]) {
                int len = x.len, cnt = x.cnt, pos = x.pos;
                update(pos, make_pair(len, cnt));
            }
            ++pos;
        }
        pair<int, int> res = get(arr[i].c); ans = combine(ans, res);
        add[arr[i].b].push_back(node(res.fi, res.se, arr[i].d));
    }
    cout << ans.fi << ' ' << ans.se;

	return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:73:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 5 ms 6740 KB Output is correct
7 Correct 6 ms 6740 KB Output is correct
8 Correct 7 ms 6868 KB Output is correct
9 Correct 11 ms 7252 KB Output is correct
10 Correct 19 ms 7784 KB Output is correct
11 Correct 24 ms 8076 KB Output is correct
12 Correct 50 ms 9648 KB Output is correct
13 Correct 58 ms 10256 KB Output is correct
14 Correct 70 ms 10924 KB Output is correct
15 Correct 79 ms 11184 KB Output is correct
16 Correct 83 ms 11532 KB Output is correct
17 Correct 86 ms 11872 KB Output is correct
18 Correct 79 ms 12148 KB Output is correct
19 Correct 95 ms 12396 KB Output is correct
20 Correct 99 ms 12736 KB Output is correct