oj.uz

Submission #945608

# Submission time Handle Problem Language Result Execution time Memory
945608 2024-03-14T05:34:59 Z vjudge1 trapezoid (balkan11_trapezoid) C++17
46 / 100
 137 ms 15060 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<<18],ans[1<<18],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
46.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 2 ms 604 KB Partially correct
5 Partially correct 2 ms 604 KB Partially correct
6 Partially correct 3 ms 860 KB Partially correct
7 Partially correct 4 ms 860 KB Partially correct
8 Partially correct 5 ms 1116 KB Partially correct
9 Partially correct 13 ms 1748 KB Partially correct
10 Partially correct 21 ms 3280 KB Partially correct
11 Partially correct 27 ms 3988 KB Partially correct
12 Partially correct 71 ms 7872 KB Partially correct
13 Partially correct 76 ms 9368 KB Partially correct
14 Partially correct 97 ms 12224 KB Partially correct
15 Partially correct 119 ms 11792 KB Partially correct
16 Partially correct 120 ms 13748 KB Partially correct
17 Partially correct 117 ms 13576 KB Partially correct
18 Partially correct 119 ms 14096 KB Partially correct
19 Partially correct 118 ms 15032 KB Partially correct
20 Partially correct 137 ms 15060 KB Partially correct