oj.uz

Submission #779783

# Submission time Handle Problem Language Result Execution time Memory
779783 2023-07-11T20:06:13 Z chanhchuong123 trapezoid (balkan11_trapezoid) C++14
22 / 100
 92 ms 15080 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());
    }
    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
22.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Partially correct 4 ms 6612 KB Partially correct
4 Incorrect 4 ms 6612 KB Output isn't correct
5 Partially correct 5 ms 6740 KB Partially correct
6 Partially correct 5 ms 6872 KB Partially correct
7 Incorrect 6 ms 6868 KB Output isn't correct
8 Incorrect 7 ms 6984 KB Output isn't correct
9 Partially correct 11 ms 7432 KB Partially correct
10 Incorrect 20 ms 8312 KB Output isn't correct
11 Incorrect 24 ms 8636 KB Output isn't correct
12 Incorrect 48 ms 10936 KB Output isn't correct
13 Incorrect 58 ms 11780 KB Output isn't correct
14 Incorrect 69 ms 12828 KB Output isn't correct
15 Incorrect 74 ms 13068 KB Output isn't correct
16 Incorrect 81 ms 13404 KB Output isn't correct
17 Incorrect 81 ms 13964 KB Output isn't correct
18 Incorrect 81 ms 14516 KB Output isn't correct
19 Partially correct 87 ms 14788 KB Partially correct
20 Partially correct 92 ms 15080 KB Partially correct