oj.uz

Submission #169452

# Submission time Handle Problem Language Result Execution time Memory
169452 2019-12-20T12:16:35 Z vex trapezoid (balkan11_trapezoid) C++14
100 / 100
 169 ms 11116 KB 
#include <bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define x first
#define y second
#define ll long long
#define mod 30013
#define MAX 200000
using namespace std;

struct djoka
{
    int x,y,type;
};

int n;
djoka niz[2*maxn];
int maxx[maxn];
ll num[maxn];

int maks[4*MAX + 5];
ll br[4*MAX + 5];
void update(int v,int l,int r,int lt,int rt,int bigg,int broj)
{
    if(l>r || l>rt || lt>r || lt>rt)return;
    if(lt<=l && r<=rt)
    {
        if(maks[v] == bigg)
        {
            br[v] += broj;
            br[v] %= mod;
        }
        else if(maks[v] < bigg)
        {
            br[v] = broj;
            maks[v] = bigg;
        }
        return;
    }
    int mid = (l+r)/2;
    update(2*v,l,mid,lt,rt,bigg,broj);
    update(2*v+1,mid+1,r,lt,rt,bigg,broj);
}
int najv(int v,int l,int r,int ind)
{
    if(l>r || l>ind || r<ind)return 0;
    if(l==r)return maks[v];
    int mid = (l+r)/2;
    if(ind<=mid)return max(maks[v],najv(2*v,l,mid,ind));
    return max(maks[v],najv(2*v+1,mid+1,r,ind));
}
ll broj(int v,int l,int r,int ind,int maksimus)
{
    if(l>r || l>ind || ind>r)return 0;
    if(l==r)
    {
        if(maks[v] == maksimus)return br[v];
        return 0;
    }
    int mid = (l+r)/2;
    ll uk = 0;
    if(maks[v] == maksimus)uk += br[v];
    if(ind<=mid)return (uk + broj(2*v,l,mid,ind,maksimus))%mod;
    return (uk + broj(2*v+1,mid+1,r,ind,maksimus))%mod;
}

bool cmp_x(djoka levi,djoka desni)
{
    if(levi.x!=desni.x)return levi.x < desni.x;
    return levi.type < desni.type;
}
bool cmp_y(djoka levi,djoka desni)
{
    if(levi.y!=desni.y)return levi.y < desni.y;
    return levi.type < desni.type;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>niz[2*i].x>>niz[2*i+1].x>>niz[2*i].y>>niz[2*i+1].y;
        niz[2*i].type = i+1;
        niz[2*i+1].type = -(i+1);
    }
    sort(niz,niz + 2*n,cmp_y);
    for(int i=0;i<2*n;i++)
    {
        niz[i].y = i;
    }
    sort(niz,niz + 2*n,cmp_x);
    for(int i=0;i<2*n;i++)
    {
        niz[i].x = i;
    }
    update(1,0,MAX,0,MAX,0,1);
    for(int i=0;i<2*n;i++)
    {
        int ind = abs(niz[i].type) - 1;
        if(niz[i].type > 0)
        {
            maxx[ind] = najv(1,0,MAX,niz[i].y) + 1;
            num[ind] = broj(1,0,MAX,niz[i].y,maxx[ind] - 1);
        }
        else
        {
            update(1,0,MAX,niz[i].y+1,MAX,maxx[ind],num[ind]);
        }
    }

    int sol_max = 0;
    ll sol_br = 0;
    for(int i=0;i<n;i++)
    {
        //cout<<maxx[i]<<" "<<num[i]<<endl;
        if(sol_max == maxx[i])
        {
            sol_br += num[i];
            sol_br %= mod;
        }
        else if(sol_max < maxx[i])
        {
            sol_br = num[i];
            sol_max = maxx[i];
        }
    }

    cout<<sol_max<<" "<<sol_br<<endl;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 7 ms 888 KB Output is correct
8 Correct 10 ms 1016 KB Output is correct
9 Correct 17 ms 1400 KB Output is correct
10 Correct 29 ms 2424 KB Output is correct
11 Correct 41 ms 2808 KB Output is correct
12 Correct 82 ms 5244 KB Output is correct
13 Correct 101 ms 6340 KB Output is correct
14 Correct 116 ms 7544 KB Output is correct
15 Correct 127 ms 8184 KB Output is correct
16 Correct 137 ms 8696 KB Output is correct
17 Correct 144 ms 9452 KB Output is correct
18 Correct 127 ms 9976 KB Output is correct
19 Correct 154 ms 9928 KB Output is correct
20 Correct 169 ms 11116 KB Output is correct