Submission #825584

#	Time	Username	Problem	Language	Result	Execution time	Memory
825584		boyliguanhan	trapezoid (balkan11_trapezoid)	C++17	60 / 100	786 ms	23120 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?c==C.c?d<C.d:c<C.c:b<C.b:a<C.a;
    }
} t[200100];
map<int, int> mp;
struct make{
    int v = 0, cnt = 0;
} tre[200100], ans[200100];
make operator + (make a, make b) {
    make c;
    c.cnt = a.cnt;
    c.v = a.v;
    if(b.v>a.v)
        c.v = b.v,c.cnt=0;
    if(b.v==c.v)
        c.cnt+=b.cnt;
    c.cnt%=30013;
    return c;
}
void upd(make x, int p) {
    while(p<200100)
        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<200100)
        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({t[i].b, t[i].d, i});
    for(int j = mid+1; j <= r; j++)
        tp.push_back({t[j].a, t[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(t[i].d);
    tp.clear();
    cdq(mid+1, r);
}
int main() {
    for(int i = 0; i < 200100; i++)
        ans[i].cnt=1;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d,mp[t[i].d],
        mp[t[i].a], mp[t[i].c], mp[t[i].b];
    int x = 0;
    for(auto &i: mp)
        i.second=++x;
    for(int i = 0; i < n; i++)
        t[i].a=mp[t[i].a], t[i].b = mp[t[i].b], t[i].c = mp[t[i].c], t[i].d = mp[t[i].d];
    sort(t, t+n);
    cdq(0,n-1);

    for(int i = 0; i < n; i++)
        ans[n]=ans[n]+ans[i], cerr << ans[i].v << ' ' << ans[i].cnt << '\n';
    cout << ans[n].v << ' ' << ans[n].cnt << '\n';
}

Compilation message (stderr)

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

• Subtask 1: 60 / 100