Submission #781680

#	Time	Username	Problem	Language	Result	Execution time	Memory
781680		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	159 ms	26416 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define OYY 1000000005
#define mod 998244353
#define mid (start+end)/2
vector <pair<int,int>> v,v2,hu,d;
int re[1000005],tree[8000005],tut[1000005];

void build(int node,int start,int end){
    if(start==end){
        tree[node]=re[start];
        return ;
    }
    build(node*2,start,mid),build(node*2+1,mid+1,end);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}

int query(int node,int start,int end,int l,int r){
    if(start>end || start>r || end<l)return 0;
    if(start>=l&& end<=r)return tree[node];
    return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}

void update(int node,int start,int end,int l,int r,int val){
    if(start>end || start>r || end<l)return ;
    if(start>=l&& end<=r){
        tree[node]=val;
        return ;
    }
    update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}

int32_t main(){
    faster
    int n;cin>>n;
    int dizi[n+1],di[n];
    for(int i=0;i<=n;i++){
        cin>>dizi[i];
        d.push_back({dizi[i],i});
    }
    for(int i=0;i<n;i++)cin>>di[i];
    sort(d.begin(),d.end());
    sort(di,di+n);
    sort(dizi,dizi+n);
    int maxi=0;
    for(int i=1;i<=n;i++){
       // cout<<dizi[i]<<" "<<di[]
        v.push_back({max(d[i].first-di[i-1],(int)0),d[i].second});
        maxi=max(maxi,v[i-1].first);
    }
    for(int i=0;i<n;i++){
        v2.push_back({max(d[i].first-di[i],(int)0),d[i].second});
    }
    for(int i=0;i<v.size();i++){
       // cout<<v[i].first<<" "<<v[i].second<<endl;
        re[i+1]=v[i].first;
        tut[i+1]=v[i].second;
       // cout<<tut[i+1]<<endl;
    }
    //for(int i=0;i<n;i++)
    build(1,1,n);
    //cout<<d[0].second<<endl;
    hu.push_back({d[0].second,maxi});
    for(int i=0;i<v.size();i++){
        update(1,1,n,i+1,i+1,v2[i].first);
        hu.push_back({tut[i+1],query(1,1,n,1,n)});
    }
    sort(hu.begin(),hu.end());
    for(int i=0;i<hu.size();i++)cout<<hu[i].second<<" ";
    cout<<endl;
    return 0;
}

Compilation message (stderr)

ho_t1.cpp: In function 'int32_t main()':
ho_t1.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
ho_t1.cpp:67:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
ho_t1.cpp:72:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<hu.size();i++)cout<<hu[i].second<<" ";
      |                 ~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91