oj.uz

Submission #825572

# Submission time Handle Problem Language Result Execution time Memory
825572 2023-08-15T03:53:19 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
33 / 100
 389 ms 22284 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?c==C.c?d<C.d:c<C.c: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 0 ms 340 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 3 ms 468 KB Partially correct
5 Partially correct 6 ms 724 KB Partially correct
6 Partially correct 8 ms 1108 KB Partially correct
7 Partially correct 10 ms 900 KB Partially correct
8 Partially correct 14 ms 1352 KB Partially correct
9 Partially correct 34 ms 2688 KB Partially correct
10 Partially correct 55 ms 3528 KB Partially correct
11 Partially correct 96 ms 6404 KB Partially correct
12 Partially correct 179 ms 12696 KB Partially correct
13 Incorrect 223 ms 14796 KB Output isn't correct
14 Incorrect 253 ms 18028 KB Output isn't correct
15 Partially correct 296 ms 16636 KB Partially correct
16 Partially correct 354 ms 17476 KB Partially correct
17 Incorrect 339 ms 20280 KB Output isn't correct
18 Partially correct 282 ms 14568 KB Partially correct
19 Incorrect 359 ms 21532 KB Output isn't correct
20 Incorrect 389 ms 22284 KB Output isn't correct