oj.uz

Submission #945806

# Submission time Handle Problem Language Result Execution time Memory
945806 2024-03-14T07:52:50 Z boyliguanhan trapezoid (balkan11_trapezoid) C++17
100 / 100
 186 ms 18332 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=(y+z.y)%30013;
    }
} 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 8 ms 1240 KB Output is correct
9 Correct 11 ms 2004 KB Output is correct
10 Correct 24 ms 3780 KB Output is correct
11 Correct 27 ms 4812 KB Output is correct
12 Correct 69 ms 9152 KB Output is correct
13 Correct 84 ms 10940 KB Output is correct
14 Correct 97 ms 12988 KB Output is correct
15 Correct 121 ms 13692 KB Output is correct
16 Correct 169 ms 15656 KB Output is correct
17 Correct 153 ms 16352 KB Output is correct
18 Correct 121 ms 16628 KB Output is correct
19 Correct 147 ms 16980 KB Output is correct
20 Correct 186 ms 18332 KB Output is correct