Submission #825569

#	Time	Username	Problem	Language	Result	Execution time	Memory
825569		boyliguanhan	trapezoid (balkan11_trapezoid)	C++17	21 / 100	194 ms	11040 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
struct trap{
    int a,b,c,d;
    bool operator < (trap c) {
        return a==c.a?b<c.b:a<c.a;
    }
} traps[200100];
struct make{
    int v = 0, cnt = 0;
    make operator + (make b) {
        make c;
        c.v = max(v, b.v);
        if(v==c.v)
            c.cnt=cnt;
        if(b.v==c.v)
            c.cnt+=b.cnt;
        c.cnt%=30013;
        return c;
    }
} tre[200100], ans[200100];
void upd(make x, int p) {
    while(p<=2e5)
        tre[p] = tre[p] + x, p+=p&-p;
}
void Upd(int p, int up) {
    while(p)
        ans[up]=ans[up]+tre[p],p-=p&-p;
}
void clear(int x) {
    while(x<=2e5)
        tre[x] = {0,0}, x+=x&-x;
}
void cdq(int l, int r) {
    if(l==r) {
        ans[l].v++;
        return;
    }
    int mid = l+r>>1;
    cdq(l, mid);
    vector<tuple<int, int, int>> tp;
    for(int i = l; i <= mid; i++)
        tp.push_back({traps[i].b, traps[i].d, i});
    for(int j = mid+1; j <= r; j++)
        tp.push_back({traps[j].a, traps[j].c, j});
    sort(tp.begin(), tp.end());
    for(auto i: tp) {
        int a, b, c;
        tie(a,b,c) = i;
        if(c<=mid)
            upd(ans[c],b);
        else
            Upd(b,c);
    }
    for(int i = l; i <= mid; i++)
        clear(traps[i].d);
    tp.clear();
    cdq(mid+1, r);
}
int main() {
    ans[0].cnt = 1;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> traps[i].a >> traps[i].b >> traps[i].c >> traps[i].d;
    sort(traps, traps+n);
    cdq(0,n-1);
    for(int i = 0; i < n; i++)
        ans[n]=ans[n]+ans[i];
    cout << ans[n].v << ' ' << ans[n].cnt << '\n';
}

Compilation message (stderr)

trapezoid.cpp: In function 'void cdq(int, int)':
trapezoid.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l+r>>1;
      |               ~^~

• Subtask 1: 21 / 100