oj.uz

Submission #825585

# Submission time Handle Problem Language Result Execution time Memory
825585 2023-08-15T05:09:17 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
60 / 100
 500 ms 23048 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[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() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 4 ms 2004 KB Output is correct
4 Correct 6 ms 2004 KB Output is correct
5 Correct 13 ms 2408 KB Output is correct
6 Correct 20 ms 2644 KB Output is correct
7 Correct 25 ms 2528 KB Output is correct
8 Correct 31 ms 2916 KB Output is correct
9 Correct 73 ms 4224 KB Output is correct
10 Correct 128 ms 4936 KB Output is correct
11 Correct 182 ms 7784 KB Output is correct
12 Correct 364 ms 13892 KB Output is correct
13 Incorrect 445 ms 15944 KB Output isn't correct
14 Execution timed out 575 ms 19328 KB Time limit exceeded
15 Execution timed out 611 ms 17612 KB Time limit exceeded
16 Execution timed out 714 ms 18644 KB Time limit exceeded
17 Execution timed out 630 ms 21300 KB Time limit exceeded
18 Execution timed out 595 ms 15412 KB Time limit exceeded
19 Execution timed out 655 ms 22344 KB Time limit exceeded
20 Execution timed out 712 ms 23048 KB Time limit exceeded