oj.uz

답안 #51893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51893 2018-06-22T12:53:13 Z someone_aa 사다리꼴 (balkan11_trapezoid) C++17
2 / 100
 500 ms 34088 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;
            }
        }
    }
}

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[(index<<1)][0] == tree[(index<<1)+1][0]) {
                tree[index][0] = tree[(index<<1)][0];
                tree[index][1] = (tree[(index<<1)][1] + tree[(index<<1)+1][1]);
                if(tree[index][1] > mod) tree[index][1] -= mod;
            }
            else if(tree[(index<<1)][0] > tree[(index<<1)+1][0]) {
                tree[index][0] = tree[(index<<1)][0];
                tree[index][1] = tree[(index<<1)][1];
            }
            else {
                tree[index][0] = tree[(index<<1)+1][0];
                tree[index][1] = tree[(index<<1)+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) >> 1;
        pii a = query(ql,qr,li,mid,index<<1);
        pii b = query(ql,qr,mid+1,ri,(index<<1)+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:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:95: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
2.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 6 ms 5112 KB Partially correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Incorrect 7 ms 5276 KB Output isn't correct
4 Incorrect 8 ms 5420 KB Output isn't correct
5 Incorrect 12 ms 5660 KB Output isn't correct
6 Incorrect 18 ms 5964 KB Output isn't correct
7 Incorrect 17 ms 6260 KB Output isn't correct
8 Incorrect 22 ms 6604 KB Output isn't correct
9 Incorrect 44 ms 8044 KB Output isn't correct
10 Incorrect 83 ms 11024 KB Output isn't correct
11 Incorrect 104 ms 12492 KB Output isn't correct
12 Incorrect 250 ms 19732 KB Output isn't correct
13 Incorrect 308 ms 22804 KB Output isn't correct
14 Incorrect 360 ms 25468 KB Output isn't correct
15 Incorrect 446 ms 26968 KB Output isn't correct
16 Execution timed out 506 ms 28560 KB Time limit exceeded
17 Execution timed out 634 ms 29968 KB Time limit exceeded
18 Incorrect 483 ms 31292 KB Output isn't correct
19 Incorrect 476 ms 32708 KB Output isn't correct
20 Execution timed out 550 ms 34088 KB Time limit exceeded