oj.uz

Submission #825569

# Submission time Handle Problem Language Result Execution time Memory
825569 2023-08-15T03:39:10 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
21 / 100
 194 ms 11040 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;
    }
} traps[200100];
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[200100], ans[200100];
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({traps[i].b, traps[i].d, i});
    for(int j = mid+1; j <= r; j++)
        tp.push_back({traps[j].a, traps[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(traps[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 >> traps[i].a >> traps[i].b >> traps[i].c >> traps[i].d;
    sort(traps, traps+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:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l+r>>1;
      |               ~^~

Subtask #1
21.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 340 KB Partially correct
5 Partially correct 4 ms 596 KB Partially correct
6 Partially correct 6 ms 1316 KB Partially correct
7 Partially correct 8 ms 1108 KB Partially correct
8 Partially correct 9 ms 680 KB Partially correct
9 Partially correct 19 ms 1180 KB Partially correct
10 Incorrect 40 ms 3168 KB Output isn't correct
11 Incorrect 49 ms 3172 KB Output isn't correct
12 Incorrect 97 ms 5444 KB Output isn't correct
13 Incorrect 115 ms 6068 KB Output isn't correct
14 Runtime error 83 ms 7276 KB Execution killed with signal 11
15 Incorrect 162 ms 7496 KB Output isn't correct
16 Incorrect 169 ms 7908 KB Output isn't correct
17 Runtime error 127 ms 11040 KB Execution killed with signal 11
18 Incorrect 187 ms 8616 KB Output isn't correct
19 Runtime error 137 ms 10936 KB Execution killed with signal 11
20 Incorrect 194 ms 8832 KB Output isn't correct