Submission #741131

#	Time	Username	Problem	Language	Result	Execution time	Memory
741131		Trent	trapezoid (balkan11_trapezoid)	C++17	100 / 100	248 ms	23560 KiB

trapezoid

#include "bits/stdc++.h"
 
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}

const int MN = 1e5 + 10, ME = 8 * MN, MOD = 30013;
struct node{int ma, cnt;};
node seg[ME];
node comb(const node a, const node b){
    node ret = {max(a.ma, b.ma), 0};
    if(a.ma == ret.ma) ret.cnt += a.cnt;
    if(b.ma == ret.ma) ret.cnt += b.cnt;
    ret.cnt %= MOD;
    return ret;
}
void upd(int i, int to, int cnt, int v, int nl, int nr){
    if(nl == nr){
        seg[v] = {to, cnt};
    } else {
        int mid = (nl + nr) / 2;
        if(i <= mid) upd(i,to,cnt, 2*v,nl,mid);
        else upd(i,to,cnt, 2*v+1,mid+1,nr);
        seg[v] = comb(seg[2*v], seg[2*v+1]);
    }
}
node qu(int l, int r, int v, int nl, int nr){
    if(nl > r || nr < l) return {0, 0};
    else if(nl == l && nr == r) return seg[v];
    else {
        int mid = (nl + nr) / 2;
        return comb(
            qu(l, min(mid, r), 2*v, nl, mid),
            qu(max(l, mid+1), r, 2*v+1, mid+1, nr)
        );
    }
}

struct trap{int a, b, c, d, ci, di;};
trap trp[MN];
struct ev{int ty, in, ti;}; // ty: 0->open, 1->close
int tma[MN], tc[MN];
signed main(){
    int n; cin >> n;
    set<int> bin;
    vector<ev> evs;
    forR(i, n) {
        cin >> trp[i].a >> trp[i].b >> trp[i].c >> trp[i].d;
        bin.insert(trp[i].c); bin.insert(trp[i].d);
        evs.push_back({0, trp[i].a, i});
        evs.push_back({1, trp[i].b, i});
    }
    vector<int> vbin; for(int i : bin) vbin.push_back(i);
    forR(i, n){
        trp[i].ci = lower_bound(all(vbin), trp[i].c) - vbin.begin() + 1;
        trp[i].di = lower_bound(all(vbin), trp[i].d) - vbin.begin() + 1;
    }
    sort(all(evs), [](ev& a, ev& b){return a.in < b.in;});
    int bs = vbin.size();
    upd(0, 0, 1, 1, 0, bs);
    for(auto [ty, in, ti] : evs){
        if(ty == 0){
            node ans = qu(0, trp[ti].ci-1, 1, 0, bs);
            // printf("%d %d [%d, %d]\n", ty, ti, ans.ma, ans.cnt);
            tma[ti] = ans.ma + 1; tc[ti] = ans.cnt;
        } else {
            // printf("%d %d [%d, %d]\n", ty, ti, tma[ti], tc[ti]);
            upd(trp[ti].di, tma[ti], tc[ti], 1, 0, bs);
        }
    }
    node ans = qu(0, bs, 1, 0, bs);
    cout << ans.ma << ' ' << ans.cnt << '\n';
}

Compilation message (stderr)

trapezoid.cpp: In function 'bool operator<(pii, pii)':
trapezoid.cpp:14:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                    ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 100 / 100