oj.uz

답안 #51882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51882 2018-06-22T11:01:49 Z someone_aa 사다리꼴 (balkan11_trapezoid) C++17
70 / 100
 500 ms 36580 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, int value, int 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() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d %d %d %d", &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);
    int result = 0;
    int ways = 0;
    for(int i=1;i<=upmax;i++) {
        for(int j=0;j<events[i].size();j++) {
            if(events[i][j].second) {
                pii temp = query(0, arr[events[i][j].first].c);
                dp[events[i][j].first] = temp.first + 1;
                dpways[events[i][j].first] = temp.second;
                if(dp[events[i][j].first] > result) {
                    result = dp[events[i][j].first];
                    ways = dpways[events[i][j].first];
                }
                else if(dp[events[i][j].first] == result) {
                    ways += dpways[events[i][j].first];
                    if(ways > mod) ways-=mod;
                }
            }
            else update(arr[events[i][j].first].d, dp[events[i][j].first], dpways[events[i][j].first]);
        }
    }
    cout<<result<<" "<<ways<<"\n";
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<events[i].size();j++) {
                     ~^~~~~~~~~~~~~~~~~
trapezoid.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &arr[i].a, &arr[i].b, &arr[i].c, &arr[i].d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4988 KB Output is correct
2 Correct 8 ms 5224 KB Output is correct
3 Correct 10 ms 5280 KB Output is correct
4 Correct 10 ms 5472 KB Output is correct
5 Correct 13 ms 5736 KB Output is correct
6 Correct 17 ms 6036 KB Output is correct
7 Correct 21 ms 6376 KB Output is correct
8 Correct 30 ms 6888 KB Output is correct
9 Correct 56 ms 8496 KB Output is correct
10 Correct 116 ms 11884 KB Output is correct
11 Correct 131 ms 13000 KB Output is correct
12 Correct 332 ms 21192 KB Output is correct
13 Correct 463 ms 23700 KB Output is correct
14 Correct 463 ms 28600 KB Output is correct
15 Execution timed out 665 ms 30184 KB Time limit exceeded
16 Execution timed out 656 ms 31344 KB Time limit exceeded
17 Execution timed out 620 ms 32720 KB Time limit exceeded
18 Execution timed out 530 ms 34160 KB Time limit exceeded
19 Execution timed out 560 ms 34940 KB Time limit exceeded
20 Execution timed out 673 ms 36580 KB Time limit exceeded