oj.uz

Submission #945607

# Submission time Handle Problem Language Result Execution time Memory
945607 2024-03-14T05:34:11 Z vjudge1 trapezoid (balkan11_trapezoid) C++17
32 / 100
 113 ms 32960 KB 
#include<bits/stdc++.h>
using namespace std;
struct C{
    int x=0,y=0;
    void operator+=(C z){
        if(x<z.x)
            x=z.x,y=0;
        if(x==z.x)
            y+=z.y;
    }
} T[1<<17],ans[1<<17],res;
map<int,int> mp;
int cnt;
void upd(int x,C z){
    while(x<=cnt)
        T[x]+=z,x+=x&-x;
}
C q(int x){
    C z;
    while(x)
        z+=T[x],x-=x&-x;
    return z;
}
priority_queue<array<int,4>,vector<array<int,4>>,greater<>>pq;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        pq.push({a,c,1,i});
        pq.push({b,d,0,i});
        mp[c],mp[d];
    }
    for(auto&[i,j]:mp)
        j=++cnt;
    upd(1,{0,1});
    while(pq.size()){
        auto[a,b,c,d]=pq.top();
        pq.pop();
        if(c)
            ans[d]=q(mp[b]),ans[d].x++;
        else
            upd(mp[b],ans[d]);
    }
    for(int i=0;i<n;i++)
        res+=ans[i];
    cout<<res.x<<' '<<res.y;
}

Subtask #1
32.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 1 ms 604 KB Partially correct
5 Partially correct 3 ms 756 KB Partially correct
6 Partially correct 3 ms 980 KB Partially correct
7 Partially correct 4 ms 1116 KB Partially correct
8 Partially correct 6 ms 1200 KB Partially correct
9 Partially correct 11 ms 1968 KB Partially correct
10 Partially correct 21 ms 3924 KB Partially correct
11 Partially correct 27 ms 4740 KB Partially correct
12 Partially correct 61 ms 9124 KB Partially correct
13 Partially correct 75 ms 10724 KB Partially correct
14 Runtime error 89 ms 25500 KB Execution killed with signal 11
15 Runtime error 89 ms 24904 KB Execution killed with signal 11
16 Runtime error 86 ms 28520 KB Execution killed with signal 11
17 Runtime error 98 ms 27316 KB Execution killed with signal 11
18 Runtime error 97 ms 30180 KB Execution killed with signal 11
19 Runtime error 97 ms 31572 KB Execution killed with signal 11
20 Runtime error 113 ms 32960 KB Execution killed with signal 11