oj.uz

Submission #722689

# Submission time Handle Problem Language Result Execution time Memory
722689 2023-04-12T16:24:03 Z groshi trapezoid (balkan11_trapezoid) C++17
46 / 100
 308 ms 32344 KB 
#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];
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;
        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;
    }
    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;
        }
    }
    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];
    }
    cout<<maxx<<" "<<mam;
    return 0;
}

Compilation message

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

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Partially correct 4 ms 5076 KB Partially correct
4 Partially correct 4 ms 5204 KB Partially correct
5 Partially correct 6 ms 5588 KB Partially correct
6 Partially correct 9 ms 5948 KB Partially correct
7 Partially correct 8 ms 5844 KB Partially correct
8 Partially correct 12 ms 6228 KB Partially correct
9 Partially correct 24 ms 7764 KB Partially correct
10 Partially correct 33 ms 8928 KB Partially correct
11 Partially correct 58 ms 12488 KB Partially correct
12 Partially correct 161 ms 19528 KB Partially correct
13 Partially correct 185 ms 22756 KB Partially correct
14 Partially correct 236 ms 26924 KB Partially correct
15 Partially correct 227 ms 24596 KB Partially correct
16 Partially correct 267 ms 26304 KB Partially correct
17 Partially correct 305 ms 30200 KB Partially correct
18 Partially correct 154 ms 22628 KB Partially correct
19 Partially correct 265 ms 31200 KB Partially correct
20 Partially correct 308 ms 32344 KB Partially correct