oj.uz

답안 #51877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51877 2018-06-22T10:12:18 Z someone_aa 사다리꼴 (balkan11_trapezoid) C++17
70 / 100
 500 ms 36604 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;
const ll mod = 30013;
map<int, int> up, down;
int tree[2*4*maxn][2];
int upmax, downmax, n;
int dp[maxn];
int dpways[maxn];

struct trapez {
public:
    int a, b, c, d;
} arr[maxn];

void update(int ux, ll value, ll valueb, int li=0, int ri=downmax, int index=1) {
    if(li==ri) {
        tree[index][0] += value;
        tree[index][1] += valueb;
        if(tree[index][1] > mod)
            tree[index][1] %= mod;
    }
    else {
        int mid = (li+ri)/2;
        if(ux <= mid) update(ux, value, valueb, li, mid, 2*index);
        else if(ux > mid) update(ux, value, valueb, mid+1, ri, 2*index+1);

        if(tree[2*index][0] == tree[2*index+1][0]) {
            tree[index][0] = tree[2*index][0];
            tree[index][1] = (tree[2*index][1] + tree[2*index+1][1]);
            if(tree[index][1] > mod) tree[index][1] %= mod;
        }
        else if(tree[2*index][0] > tree[2*index+1][0]) {
            tree[index][0] = tree[2*index][0];
            tree[index][1] = tree[2*index][1];
        }
        else {
            tree[index][0] = tree[2*index+1][0];
            tree[index][1] = tree[2*index+1][1];
        }
    }
}

pii query(int ql, int qr, int li=0, int ri=downmax, int index=1) {
    if(li > qr || ri < ql) return make_pair(0, 0);
    else if(li >= ql && ri <= qr) return make_pair(tree[index][0], tree[index][1]);
    else {
        int mid = (li+ri)/2;
        pii a = query(ql,qr,li,mid,2*index);
        pii b = query(ql,qr,mid+1,ri,2*index+1);

        if(a.first == b.first) return make_pair(a.first, (a.second+b.second)%mod);
        else if(a.first > b.first) return a;
        else return b;
    }
}

vector<pair<int, bool> > events[2*maxn];

int main() {
    //ifstream fin;
    //fin.open("input.txt");

    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>arr[i].a>>arr[i].b>>arr[i].c>>arr[i].d;
        up[arr[i].a] = 1;
        up[arr[i].b] = 1;
        down[arr[i].c] = 1;
        down[arr[i].d] = 1;
    }

    upmax = downmax = 1;
    for(auto i:up) {
        up[i.first] = upmax++;
    }
    for(auto i:down) {
        down[i.first] = downmax++;
    }

    for(int i=0;i<n;i++) {
        arr[i].a = up[arr[i].a];
        arr[i].b = up[arr[i].b];
        arr[i].c = down[arr[i].c];
        arr[i].d = down[arr[i].d];

        events[arr[i].a].push_back(make_pair(i, true));
        events[arr[i].b].push_back(make_pair(i, false));
    }

    update(0,0,1);
    for(int i=1;i<=upmax;i++) {
        for(auto j:events[i]) {
            if(j.second) {
                pii temp = query(0, arr[j.first].c);
                dp[j.first] = temp.first + 1;
                dpways[j.first] = temp.second;
            }
            else update(arr[j.first].d, dp[j.first], dpways[j.first]);
        }
    }

    int result = 0;
    int ways = 0;
    for(int i=0;i<n;i++) {
        if(dp[i] > result) {
            result = dp[i];
            ways = dpways[i];
        }
        else if(dp[i] == result) {
            ways += dpways[i];
            if(ways > mod)
                ways %= mod;
        }
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Subtask #1
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5276 KB Output is correct
4 Correct 9 ms 5480 KB Output is correct
5 Correct 14 ms 5864 KB Output is correct
6 Correct 17 ms 6128 KB Output is correct
7 Correct 25 ms 6452 KB Output is correct
8 Correct 33 ms 6964 KB Output is correct
9 Correct 63 ms 8500 KB Output is correct
10 Correct 138 ms 11784 KB Output is correct
11 Correct 199 ms 13096 KB Output is correct
12 Correct 337 ms 21100 KB Output is correct
13 Correct 416 ms 23916 KB Output is correct
14 Correct 455 ms 28536 KB Output is correct
15 Execution timed out 562 ms 29964 KB Time limit exceeded
16 Execution timed out 658 ms 31492 KB Time limit exceeded
17 Execution timed out 591 ms 32620 KB Time limit exceeded
18 Execution timed out 574 ms 33908 KB Time limit exceeded
19 Execution timed out 600 ms 34916 KB Time limit exceeded
20 Execution timed out 768 ms 36604 KB Time limit exceeded