oj.uz

Submission #825571

# Submission time Handle Problem Language Result Execution time Memory
825571 2023-08-15T03:50:36 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
6 / 100
 409 ms 22436 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-1, t[i].d-1, 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
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 2 ms 468 KB Output isn't correct
5 Incorrect 5 ms 840 KB Output isn't correct
6 Incorrect 8 ms 1024 KB Output isn't correct
7 Incorrect 10 ms 860 KB Output isn't correct
8 Incorrect 15 ms 1368 KB Output isn't correct
9 Incorrect 31 ms 2688 KB Output isn't correct
10 Partially correct 57 ms 3536 KB Partially correct
11 Incorrect 81 ms 6440 KB Output isn't correct
12 Incorrect 187 ms 12608 KB Output isn't correct
13 Incorrect 227 ms 14720 KB Output isn't correct
14 Incorrect 260 ms 18028 KB Output isn't correct
15 Partially correct 324 ms 16736 KB Partially correct
16 Partially correct 349 ms 17568 KB Partially correct
17 Incorrect 336 ms 20260 KB Output isn't correct
18 Incorrect 284 ms 14604 KB Output isn't correct
19 Incorrect 363 ms 21468 KB Output isn't correct
20 Incorrect 409 ms 22436 KB Output isn't correct