Submission #722690

#	Time	Username	Problem	Language	Result	Execution time	Memory
722690		groshi	trapezoid (balkan11_trapezoid)	C++17	100 / 100	311 ms	29604 KiB

trapezoid

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;
int x1[200000],y1[200000],x2[200000],y2[200000];
vector<int> pytaj[200000];
int wynik[200000];
int ile[200000];
map<int,int> mapka;
vector<pair<int,int> > Q;
vector<int> zero;
int pot=1;
int maxxx[2000000];
int ilee[2000000];
int mod=30013;
pair<int,int> combine(int x1,int x2,int y1,int y2)
{
    if(x1!=x2)
    {
        if(x1>x2)
            return {x1,y1};
        else return {x2,y2};
    }
    else return {x1,y1+y2};
}
void ustaw(int x,int maxx,int ile)
{
    x+=pot;
    maxxx[x]=maxx;
    ilee[x]=ile;
    x/=2;
    while(x>0)
    {
        pair<int,int> para=combine(maxxx[x*2],maxxx[x*2+1],ilee[x*2],ilee[x*2+1]);
        maxxx[x]=para.first;
        ilee[x]=para.second;
        ilee[x]%=mod;
        x/=2;
    }
}
pair<int,int> zap(int x,int y)
{
    x+=pot;
    y+=pot;
    pair<int,int> wynik;
    if(x!=y)
        wynik=combine(maxxx[x],maxxx[y],ilee[x],ilee[y]);
    else wynik={maxxx[x],ilee[x]};
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik=combine(wynik.first,maxxx[x+1],wynik.second,ilee[x+1]);
        if(y%2==1)
            wynik=combine(wynik.first,maxxx[y-1],wynik.second,ilee[y-1]);
        x/=2;
        y/=2;
        wynik.second%=mod;
    }
    wynik.second%=mod;
    if(wynik.first==0)
        return {0,1};
    return wynik;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
    for(int i=1;i<=n;i++)
    {
        mapka[x1[i]]=1;
        mapka[y1[i]]=1;
        mapka[x2[i]]=1;
        mapka[y2[i]]=1;
    }
    int mam=1;
    for(auto it=mapka.begin();it!=mapka.end();it++)
        mapka[it->first]=mam++;
    while(pot<=mam)
        pot*=2;
    pot--;
    for(int i=1;i<=n;i++)
        Q.push_back({y1[i],i});
    sort(Q.begin(),Q.end());
    for(int i=0;i<Q.size();i++)
    {
        int pocz=0,kon=i,sre,ostd=-1;
        while(pocz<kon)
        {
            sre=(pocz+kon)/2;
            if(y1[Q[sre].second]<x1[Q[i].second])
            {
                ostd=sre;
                pocz=sre+1;
            }
            else kon=sre;
        }
        if(ostd>=0)
            pytaj[ostd].push_back(i);
        else zero.push_back(i);
    }
    for(int i=0;i<zero.size();i++)
    {
        int kto=zero[i];
        wynik[kto]=1;
        ile[kto]=1;
    }
    for(int i=0;i<Q.size();i++)
    {
        int kto=Q[i].second;
        ustaw(mapka[y2[kto]],wynik[i],ile[i]);
        for(int j=0;j<pytaj[i].size();j++)
        {
            int pytam=pytaj[i][j];
            pair<int,int> para=zap(1,mapka[x2[Q[pytam].second]]);
            wynik[pytam]=para.first+1;
            ile[pytam]=para.second;
            ile[pytam]%=mod;
        }
    }
    int maxx=1;
    mam=0;
    for(int i=0;i<n;i++)
    {
        if(wynik[i]>maxx)
        {
            mam=ile[i];
            maxx=wynik[i];
        }
        else if(wynik[i]==maxx)
            mam+=ile[i];
    }
    mam%=mod;
    cout<<maxx<<" "<<mam;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<Q.size();i++)
      |                 ~^~~~~~~~~
trapezoid.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0;i<zero.size();i++)
      |                 ~^~~~~~~~~~~~
trapezoid.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0;i<Q.size();i++)
      |                 ~^~~~~~~~~
trapezoid.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j=0;j<pytaj[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100