oj.uz

답안 #51886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51886 2018-06-22T11:30:11 Z someone_aa 사다리꼴 (balkan11_trapezoid) C++17
30 / 100
 500 ms 35760 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];

int zeroval;

void find_zero() {
    int ux = 0;
    int li = 0;
    int ri = downmax;
    int i =1;
    for(i=1;i<4*2*maxn;) {
        if(li == ri) {
            break;
        }
        else {
            int mid = (li+ri)/2;
            if(ux <= mid) {
                ri = mid;
                i = i * 2;
            }
            else if(ux > mid) {
                li = mid + 1;
                i = i * 2 + 1;
            }
        }
    }
    zeroval = i;
}

void update(int ux, int value, int valueb) {
    int index = ux + zeroval;
    while(index > 0) {
        if(index == ux+zeroval) {
            tree[index][0] += value;
            tree[index][1] += valueb;
            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] + 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];
            }
        }
        index /= 2;
    }
}

pii emp;

pii query(int ql, int qr, int li=0, int ri=downmax, int index=1) {
    if(li > qr || ri < ql) return emp;
    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() {
    emp.first = 0;
    emp.second = 0;
    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));
    }
    find_zero();
    update(0,0,1);
   // cout<<query(0,0).second;
    int result = 0;
    int ways = 0;
    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;
                if(dp[j.first] > result) {
                    result = dp[j.first];
                    ways = dpways[j.first];
                }
                else if(dp[j.first] == result) {
                    ways += dpways[j.first];
                    if(ways > mod) ways-=mod;
                }
            }
            else update(arr[j.first].d, dp[j.first], dpways[j.first]);
        }
    }
    printf("%d %d", result, ways);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:96: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
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5156 KB Output is correct
3 Incorrect 7 ms 5276 KB Output isn't correct
4 Correct 8 ms 5452 KB Output is correct
5 Incorrect 15 ms 5840 KB Output isn't correct
6 Incorrect 13 ms 6164 KB Output isn't correct
7 Correct 20 ms 6420 KB Output is correct
8 Incorrect 25 ms 6656 KB Output isn't correct
9 Incorrect 61 ms 8320 KB Output isn't correct
10 Correct 88 ms 11264 KB Output is correct
11 Incorrect 118 ms 12800 KB Output isn't correct
12 Incorrect 252 ms 20480 KB Output isn't correct
13 Incorrect 325 ms 23644 KB Output isn't correct
14 Incorrect 377 ms 26660 KB Output isn't correct
15 Execution timed out 559 ms 28140 KB Time limit exceeded
16 Execution timed out 582 ms 29728 KB Time limit exceeded
17 Execution timed out 522 ms 31180 KB Time limit exceeded
18 Correct 441 ms 32804 KB Output is correct
19 Incorrect 467 ms 33992 KB Output isn't correct
20 Execution timed out 546 ms 35760 KB Time limit exceeded