oj.uz

답안 #51874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51874 2018-06-22T10:06:37 Z someone_aa 사다리꼴 (balkan11_trapezoid) C++17
42 / 100
 500 ms 36728 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;
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;
    }
    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];
        }
        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);
        else if(a.first > b.first) return a;
        else return b;
    }
}

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

int main() {
    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];
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Subtask #1
42.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5092 KB Output is correct
3 Partially correct 7 ms 5424 KB Partially correct
4 Partially correct 10 ms 5504 KB Partially correct
5 Partially correct 14 ms 5824 KB Partially correct
6 Partially correct 20 ms 6208 KB Partially correct
7 Partially correct 16 ms 6408 KB Partially correct
8 Partially correct 22 ms 6976 KB Partially correct
9 Partially correct 41 ms 8520 KB Partially correct
10 Partially correct 77 ms 11720 KB Partially correct
11 Partially correct 93 ms 13020 KB Partially correct
12 Partially correct 259 ms 21144 KB Partially correct
13 Partially correct 303 ms 23768 KB Partially correct
14 Partially correct 380 ms 28436 KB Partially correct
15 Partially correct 446 ms 30084 KB Partially correct
16 Partially correct 479 ms 31352 KB Partially correct
17 Execution timed out 534 ms 32772 KB Time limit exceeded
18 Partially correct 420 ms 34040 KB Partially correct
19 Partially correct 464 ms 34924 KB Partially correct
20 Execution timed out 595 ms 36728 KB Time limit exceeded