oj.uz

Submission #825570

# Submission time Handle Problem Language Result Execution time Memory
825570 2023-08-15T03:46:15 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
33 / 100
 406 ms 22384 KB 
#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;
    }
} t[400100];
map<int, int> mp;
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[400100], ans[400100];
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({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() {
    ans[0].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];
    cout << ans[n].v << ' ' << ans[n].cnt << '\n';
}

Compilation message

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

Subtask #1
33.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Partially correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 2 ms 468 KB Partially correct
5 Partially correct 7 ms 824 KB Partially correct
6 Partially correct 8 ms 1028 KB Partially correct
7 Partially correct 10 ms 880 KB Partially correct
8 Partially correct 15 ms 1268 KB Partially correct
9 Partially correct 30 ms 2752 KB Partially correct
10 Partially correct 63 ms 3420 KB Partially correct
11 Partially correct 82 ms 6428 KB Partially correct
12 Partially correct 178 ms 12728 KB Partially correct
13 Incorrect 234 ms 14792 KB Output isn't correct
14 Incorrect 285 ms 17924 KB Output isn't correct
15 Partially correct 302 ms 16684 KB Partially correct
16 Partially correct 327 ms 17460 KB Partially correct
17 Incorrect 373 ms 20296 KB Output isn't correct
18 Partially correct 282 ms 14624 KB Partially correct
19 Incorrect 375 ms 21520 KB Output isn't correct
20 Incorrect 406 ms 22384 KB Output isn't correct