oj.uz

답안 #51878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51878 2018-06-22T10:14:47 Z someone_aa 사다리꼴 (balkan11_trapezoid) C++17
80 / 100
 500 ms 36644 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");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    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
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 6 ms 5296 KB Output is correct
4 Correct 8 ms 5444 KB Output is correct
5 Correct 10 ms 5696 KB Output is correct
6 Correct 13 ms 6080 KB Output is correct
7 Correct 17 ms 6516 KB Output is correct
8 Correct 23 ms 6868 KB Output is correct
9 Correct 61 ms 8496 KB Output is correct
10 Correct 84 ms 11884 KB Output is correct
11 Correct 109 ms 13108 KB Output is correct
12 Correct 251 ms 21100 KB Output is correct
13 Correct 310 ms 23920 KB Output is correct
14 Correct 389 ms 28544 KB Output is correct
15 Correct 489 ms 30076 KB Output is correct
16 Execution timed out 524 ms 31464 KB Time limit exceeded
17 Execution timed out 544 ms 32724 KB Time limit exceeded
18 Correct 457 ms 34144 KB Output is correct
19 Execution timed out 513 ms 34816 KB Time limit exceeded
20 Execution timed out 608 ms 36644 KB Time limit exceeded