oj.uz

Submission #825584

# Submission time Handle Problem Language Result Execution time Memory
825584 2023-08-15T05:08:30 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
60 / 100
 500 ms 23120 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() {
    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 2008 KB Output is correct
4 Correct 7 ms 2004 KB Output is correct
5 Correct 13 ms 2376 KB Output is correct
6 Correct 20 ms 2680 KB Output is correct
7 Correct 26 ms 2492 KB Output is correct
8 Correct 34 ms 2908 KB Output is correct
9 Correct 69 ms 4172 KB Output is correct
10 Correct 135 ms 4956 KB Output is correct
11 Correct 175 ms 7816 KB Output is correct
12 Correct 369 ms 13756 KB Output is correct
13 Incorrect 448 ms 15876 KB Output isn't correct
14 Execution timed out 521 ms 19308 KB Time limit exceeded
15 Execution timed out 601 ms 17580 KB Time limit exceeded
16 Execution timed out 646 ms 18628 KB Time limit exceeded
17 Execution timed out 666 ms 21180 KB Time limit exceeded
18 Execution timed out 659 ms 15388 KB Time limit exceeded
19 Execution timed out 720 ms 22424 KB Time limit exceeded
20 Execution timed out 786 ms 23120 KB Time limit exceeded