Submission #921472

#	Time	Username	Problem	Language	Result	Execution time	Memory
921472		eggx50000	trapezoid (balkan11_trapezoid)	C++14	2 / 100	75 ms	9820 KiB

trapezoid

#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 (stderr)

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 100