oj.uz

Submission #675966

# Submission time Handle Problem Language Result Execution time Memory
675966 2022-12-28T16:36:44 Z alexdd trapezoid (balkan11_trapezoid) C++17
100 / 100
 218 ms 28600 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int MOD = 30013;
struct event
{
    int tip;///1 - latura stanga
            ///2 - latura dreapta
    int pozs,pozj;
    int index;
};
bool cmp(event x, event y)
{
    return x.pozs < y.pozs;
}
struct node
{
    int mxm;
    int cntm;
};
node combine(node x, node y)
{
    node aux;
    aux.mxm = max(x.mxm,y.mxm);
    aux.cntm=0;
    if(x.mxm == aux.mxm)
        aux.cntm += x.cntm;
    if(y.mxm == aux.mxm)
        aux.cntm += y.cntm;
    aux.cntm %= MOD;
    return aux;
}
int n;
int a[100001];
int b[100001];
int c[100001];
int d[100001];
vector<event> events;
map<int,int> mp;
map<int,int> nor;
int cntn=0;
int rez[100001];
int cntrez[100001];
void normalizare_c_d()
{
    for(int i=0;i<n;i++)
    {
        mp[c[i]]++;
        mp[d[i]]++;
    }
    int val;
    for(auto it:mp)
    {
        val=it.first;
        cntn++;
        nor[val]=cntn;
    }
    for(int i=0;i<n;i++)
    {
        c[i]=nor[c[i]];
        d[i]=nor[d[i]];
    }
}
node aint[810000];
void upd(int nod, int st, int dr, int poz, node newval)
{
    if(st==dr)
    {
        aint[nod]=newval;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd(nod*2,st,mij,poz,newval);
    else
        upd(nod*2+1,mij+1,dr,poz,newval);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {0,0};
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                  qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    normalizare_c_d();
    for(int i=0;i<n;i++)
    {
        events.push_back({1,a[i],c[i],i});
        events.push_back({2,b[i],d[i],i});
    }
    sort(events.begin(),events.end(),cmp);
    for(auto e:events)
    {
        if(e.tip==1)
        {
            node x = qry(1,1,cntn,1,e.pozj-1);
            rez[e.index] = x.mxm + 1;
            cntrez[e.index] = max(1, x.cntm);
        }
        else
            upd(1,1,cntn,e.pozj,{rez[e.index],cntrez[e.index]});
    }
    int mxmr=0,cntr=0;
    for(int i=0;i<n;i++)
    {
        if(rez[i]>mxmr)
        {
            mxmr=rez[i];
            cntr=cntrez[i];
        }
        else if(rez[i]==mxmr)
            cntr+=cntrez[i],cntr%=MOD;
    }
    cout<<mxmr<<" "<<cntr%MOD<<"\n";
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct
7 Correct 8 ms 1492 KB Output is correct
8 Correct 8 ms 1880 KB Output is correct
9 Correct 19 ms 3324 KB Output is correct
10 Correct 43 ms 6296 KB Output is correct
11 Correct 55 ms 7372 KB Output is correct
12 Correct 131 ms 14540 KB Output is correct
13 Correct 125 ms 16980 KB Output is correct
14 Correct 154 ms 21424 KB Output is correct
15 Correct 173 ms 22696 KB Output is correct
16 Correct 190 ms 23856 KB Output is correct
17 Correct 200 ms 25148 KB Output is correct
18 Correct 204 ms 26212 KB Output is correct
19 Correct 200 ms 26932 KB Output is correct
20 Correct 218 ms 28600 KB Output is correct