답안 #921472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921472 2024-02-03T23:45:08 Z eggx50000 사다리꼴 (balkan11_trapezoid) C++14
2 / 100
75 ms 9820 KB
#include <iostream>
#include <algorithm>
#include <stack>
#include <string.h>
using namespace std;
using ll = long long;
const ll mod = 30013;


int n, a, b, c, d, cn, ec;

ll comp[200099];

struct Da{
    ll ma, cn;

    Da operator +(const Da &k){
        Da tmp;
        tmp.ma = max(ma, k.ma);
        if(ma == k.ma) tmp.cn = (cn + k.cn) % mod;
        else if(ma > k.ma) tmp.cn = cn;
        else tmp.cn = k.cn;
        return tmp;
    }

    Da pp(){
        Da tmp = {ma + 1, cn};
        return tmp;
    }


};
Da res[100099];

struct Eve{
    int t, ind, ui, x, y;

    bool operator <(const Eve &a) const{
        return ui < a.ui;
    }

} events[200099];

struct Segtree{
    Da tree[800099];
    void update(int node, int s, int e, int qi, Da qv){
        if(qi < s || e < qi) return;
        if(s == e){
            tree[node] = tree[node] + qv;
            return;
        }
        int mid = (s + e) / 2;
        update(node * 2, s, mid, qi, qv);
        update(node * 2 + 1, mid + 1, e, qi, qv);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    Da query(int node, int s, int e, int qs, int qe){
        if(qe < s || e < qs) return {0, 0};
        if(qs <= s && e <= qe) return tree[node];
        int mid = (s + e) / 2;
        return query(node * 2, s, mid, qs, qe) + query( node * 2 + 1, mid + 1, e, qs, qe);
    }

} bsegt;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d %d %d %d", &a, &b, &c, &d);
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);
        comp[++cn] = c;
        comp[++cn] = d;
        events[++ec] = {1, i, a, c, d};
        events[++ec] = {2, i, b, c, d};
    }
    sort(events + 1, events + ec + 1);
    for(int i = 1; i <= ec; i ++){
        events[i].x = lower_bound(comp + 1, comp + cn + 1, events[i].x) - comp;
        events[i].y = lower_bound(comp + 1, comp + cn + 1, events[i].y) - comp;
        if(events[i].t == 1){
            res[events[i].ind] = bsegt.query(1, 1, cn, 1, events[i].x - 1).pp();
            if(res[events[i].ind].ma == 1) res[events[i].ind].cn = 1;
        }
        else{
            bsegt.update(1, 1, cn, events[i].y, res[events[i].ind]);
        }
    }
    Da ret = {0, 1};
    for(int i = 1; i <= n; i ++){
        ret = ret + res[i];
    }
    printf("%lld %lld", ret.ma, ret.cn);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
trapezoid.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d %d %d", &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 6492 KB Partially correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Incorrect 2 ms 6492 KB Output isn't correct
5 Incorrect 3 ms 6492 KB Output isn't correct
6 Incorrect 3 ms 6748 KB Output isn't correct
7 Incorrect 4 ms 6748 KB Output isn't correct
8 Incorrect 5 ms 6488 KB Output isn't correct
9 Incorrect 8 ms 6844 KB Output isn't correct
10 Incorrect 17 ms 7000 KB Output isn't correct
11 Incorrect 18 ms 7260 KB Output isn't correct
12 Incorrect 36 ms 7772 KB Output isn't correct
13 Incorrect 43 ms 7960 KB Output isn't correct
14 Incorrect 54 ms 8540 KB Output isn't correct
15 Incorrect 58 ms 9820 KB Output isn't correct
16 Incorrect 56 ms 7760 KB Output isn't correct
17 Incorrect 63 ms 8532 KB Output isn't correct
18 Incorrect 61 ms 9296 KB Output isn't correct
19 Incorrect 69 ms 9180 KB Output isn't correct
20 Incorrect 75 ms 8792 KB Output isn't correct