oj.uz

Submission #920503

# Submission time Handle Problem Language Result Execution time Memory
920503 2024-02-02T16:10:25 Z ttamx trapezoid (balkan11_trapezoid) C++14
14 / 100
 105 ms 9040 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;
const int M=2e5+5;

int n;
int v1[M],v2[M],id1[N],id2[N];

struct Trapezoid{
    int a,b,c,d;
    Trapezoid(){};
}t[N];

struct Info{
    int val;
    long long freq;
    Info():val(0),freq(0){}
    Info(int _val,long long _freq):val(_val),freq(_freq){}
    friend Info operator+(const Info &lhs,const Info &rhs){
        if(lhs.val>rhs.val)return lhs;
        if(lhs.val<rhs.val)return rhs;
        return Info(lhs.val,lhs.freq+rhs.freq);
    }
    Info &operator+=(const Info &rhs){
        *this=*this+rhs;
        return *this;
    }
}dp[N];

struct fenwick{
    Info t[M];
    void update(int i,Info v){
        for(;i<M;i+=i&-i)t[i]+=v;
    }
    Info query(int i){
        Info res{};
        for(;i;i-=i&-i)res+=t[i];
        return res;
    }
}f;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d;
        v1[i*2-1]=t[i].a;
        v1[i*2]=t[i].b;
        v2[i*2-1]=t[i].c;
        v2[i*2]=t[i].d;
    }
    sort(v1+1,v1+2*n+1);
    sort(v2+1,v2+2*n+1);
    for(int i=1;i<=n;i++){
        t[i].a=lower_bound(v1+1,v1+2*n+1,t[i].a)-v1;
        t[i].b=lower_bound(v1+1,v1+2*n+1,t[i].b)-v1;
        t[i].c=lower_bound(v2+1,v2+2*n+1,t[i].c)-v2;
        t[i].d=lower_bound(v2+1,v2+2*n+1,t[i].d)-v2;
    }
    iota(id1+1,id1+n+1,1);
    iota(id2+1,id2+n+1,1);
    sort(id1+1,id1+n+1,[&](int i,int j){return t[i].a<t[j].a;});
    sort(id2+1,id2+n+1,[&](int i,int j){return t[i].b<t[j].b;});
    Info ans{};
    for(int _i=1,p=1;_i<=n;_i++){
        int i=id1[_i];
        while(t[id2[p]].b<t[i].a){
            f.update(t[id2[p]].d,dp[id2[p]]);
            p++;
        }
        dp[i]=f.query(t[i].c-1);
        dp[i].val++;
        if(dp[i].freq==0)dp[i].freq=1;
        ans+=dp[i];
    }
    cout << ans.val << " " << ans.freq;
}

Subtask #1
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 2 ms 8796 KB Expected int32, but "10313130667392" found
4 Incorrect 2 ms 8628 KB Expected int32, but "-8550276992825950208" found
5 Partially correct 3 ms 8796 KB Partially correct
6 Incorrect 4 ms 8796 KB Expected int32, but "-8629080777422869056" found
7 Incorrect 6 ms 8796 KB Expected int32, but "-3319866744691032064" found
8 Partially correct 6 ms 8792 KB Partially correct
9 Incorrect 11 ms 8792 KB Expected int32, but "2248786528710863832" found
10 Incorrect 20 ms 8796 KB Expected int32, but "-5022802232222890496" found
11 Incorrect 23 ms 8792 KB Expected int32, but "-1298419000938405298" found
12 Incorrect 48 ms 8796 KB Expected int32, but "9183932486774365824" found
13 Incorrect 60 ms 8796 KB Expected int32, but "-4195152448689438272" found
14 Incorrect 71 ms 8796 KB Expected int32, but "-3175106568905838848" found
15 Incorrect 78 ms 8796 KB Expected int32, but "-8026369531311511552" found
16 Incorrect 83 ms 8796 KB Expected int32, but "6233362917342126368" found
17 Incorrect 90 ms 8792 KB Expected int32, but "-7505826292837535760" found
18 Incorrect 84 ms 8976 KB Expected int32, but "-6197299359079266322" found
19 Incorrect 105 ms 9016 KB Expected int32, but "5619696618904563712" found
20 Incorrect 101 ms 9040 KB Expected int32, but "-335818733633578353" found