oj.uz

답안 #1033213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033213 2024-07-24T14:20:56 Z raphaelp 사다리꼴 (balkan11_trapezoid) C++14
18 / 100
 331 ms 32884 KB 
#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
    vector<int> st, count;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int L, int R, int a, int val, int c, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            st[x] = val;
            count[x] = c;
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, c, l(x));
            update(m + 1, R, a, val, c, r(x));
            st[x] = max(st[l(x)], st[r(x)]);
            count[x] = ((st[l(x)] == st[x]) ? count[l(x)] : 0) + ((st[r(x)] == st[x]) ? count[r(x)] : 0);
        }
    }
    pair<int, int> RSQ(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return {0, 0};
        if (L >= a && R <= b)
            return {st[x], count[x]};
        int m = (L + R) / 2;
        pair<int, int> temp1 = RSQ(L, m, a, b, l(x)), temp2 = RSQ(m + 1, R, a, b, r(x));
        if (temp1.first < temp2.first)
            swap(temp1, temp2);
        if (temp1.first == temp2.first)
            temp1.second += temp2.second;
        return temp1;
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 0);
        count.assign(2 * N, 0);
    }
    void update(int x, int val, int c) { update(0, N - 1, x, val, c, 1); }
    pair<int, int> RSQ(int a, int b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
    int N;
    cin >> N;
    vector<vector<int>> Tab;
    vector<int> vals;
    for (int i = 0; i < N; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vals.push_back(a), vals.push_back(b), vals.push_back(c), vals.push_back(d);
        Tab.push_back({a, c, b, d});
    }
    sort(vals.begin(), vals.end());
    sort(Tab.begin(), Tab.end());
    map<int, int> M;
    for (int i = 0; i < vals.size(); i++)
    {
        M[vals[i]] = i;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 4; j++)
            Tab[i][j] = M[Tab[i][j]];
    }
    SegTree ST(4 * N);
    priority_queue<vector<int>> PQ;
    vector<pair<int, int>> ans(N);
    pair<int, int> ans2 = {0, 0};
    for (int i = 0; i < N; i++)
    {
        while (!PQ.empty() && -PQ.top()[0] < Tab[i][0])
        {
            ST.update(PQ.top()[1], PQ.top()[2], PQ.top()[3]);
            PQ.pop();
        }
        ans[i] = ST.RSQ(0, Tab[i][1]);
        ans[i].first++;
        if (ans[i].first == 1)
            ans[i].second++;
        ans[i].second = ans[i].second % 30013;
        PQ.push({Tab[i][2], Tab[i][3], ans[i].first, ans[i].second});
        if (ans[i].first > ans2.first)
            ans2 = {ans[i].first, 0};
        if (ans[i].first == ans2.first)
            ans2.second += ans[i].second;
    }
    cout << ans2.first << ' ' << ans2.second;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < vals.size(); i++)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
18.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Partially correct 2 ms 600 KB Partially correct
5 Incorrect 4 ms 924 KB Output isn't correct
6 Incorrect 6 ms 1372 KB Output isn't correct
7 Partially correct 7 ms 1372 KB Partially correct
8 Incorrect 10 ms 1968 KB Output isn't correct
9 Incorrect 22 ms 4052 KB Output isn't correct
10 Partially correct 39 ms 6308 KB Partially correct
11 Incorrect 64 ms 9020 KB Output isn't correct
12 Incorrect 123 ms 18484 KB Output isn't correct
13 Incorrect 137 ms 19764 KB Output isn't correct
14 Incorrect 197 ms 28204 KB Output isn't correct
15 Incorrect 186 ms 26152 KB Output isn't correct
16 Incorrect 205 ms 26664 KB Output isn't correct
17 Incorrect 273 ms 30636 KB Output isn't correct
18 Partially correct 189 ms 24104 KB Partially correct
19 Incorrect 246 ms 31276 KB Output isn't correct
20 Incorrect 331 ms 32884 KB Output isn't correct