제출 #1046040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046040		ivopav	금 캐기 (IZhO14_divide)	C++17	100 / 100	108 ms	66468 KiB

divide

#include <bits/stdc++.h>
using namespace std;

struct node{
    long long int val;
    long long int l;
    long long int r;
};

struct camp{
    long long int x;
    long long int ene;
    long long int prefene;
    long long int prefgold;
    long long int ind;
};

bool operator<(camp c1,camp c2){
    if (c1.prefene-c1.x==c2.prefene-c2.x){
        return c1.ind>c2.ind;
    }
    return c1.prefene-c1.x>c2.prefene-c2.x;
}

void upd(long long int poc,long long int ind,long long int val,vector<node>& tour,vector<long long int>& rootind,long long int ofs){
    ind+=ofs;
    vector<pair<long long int,bool>> indlis={{ind,0}};
    while (ind>1){
        bool pom=ind%2;
        ind/=2;
        indlis.push_back({ind,pom});
    }
    reverse(indlis.begin(),indlis.end());
    bool zaddir=0;
    rootind.push_back(tour.size());
    long long int sadind=poc;
    vector<long long int> indlis2={};
    for (long long int i=0;i<indlis.size();i++){
        if (i>0){
            if (zaddir==0){
                sadind=tour[indlis2.back()].l;
                tour[indlis2.back()].l=tour.size();
            }
            else {
                sadind=tour[indlis2.back()].r;
                tour[indlis2.back()].r=tour.size();
            }
        }
        indlis2.push_back(tour.size());
        tour.push_back(tour[sadind]);
        zaddir=indlis[i].second;
    }
    tour[indlis2.back()].val=val;
    reverse(indlis2.begin(),indlis2.end());
    for (long long int i=1;i<indlis2.size();i++){
        tour[indlis2[i]].val=max(tour[tour[indlis2[i]].l].val,tour[tour[indlis2[i]].r].val);
    }
}

long long int que(long long int l,long long int r,long long int l2,long long int r2,long long int ind,vector<node>& tour){
    if (l>r2 || l2>r){
        return 0;
    }
    if (l<=l2 && r2<=r){
        return tour[ind].val;
    }
    return max(que(l,r,l2,(l2+r2)/2,tour[ind].l,tour),que(l,r,(l2+r2)/2+1,r2,tour[ind].r,tour));
}

void isp(long long int ind2,long long int ofs,vector<node>& tour,long long int ind){
    cout << tour[ind].val << "\n";
    if (ind2<ofs){
        cout << "<\n";
        isp(ind2*2,ofs,tour,tour[ind].l);
        cout << ">\n";
        isp(ind2*2+1,ofs,tour,tour[ind].r);
        
    }
    cout << "^\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    long long int n;
    cin >> n;
    vector<long long int> rootind={1};
    vector<node> tour={{0,0,0},{0,0,0}};
    long long int ofs=1;
    while (ofs<n+1){
        ofs*=2;
    }
    vector<camp> lis={};

    long long int zadgol=0;
    long long int zadene=0;
    for (long long int i=0;i<n;i++){
        long long int x;
        long long int gol;
        long long int ene;
        cin >> x >> gol >> ene;
        zadgol+=gol;
        zadene+=ene;
        lis.push_back({x,ene,zadene,zadgol,i});
    }
    vector<camp> sortlis=lis;
    sort(sortlis.begin(),sortlis.end());
    set<pair<long long int,long long int>> lisval={};
    for (long long int i=0;i<n;i++){
        upd(rootind.back(),sortlis[i].ind,sortlis[i].ind+1,tour,rootind,ofs);
    //    cout << sortlis[i].x << " " << sortlis[i].prefene << "\n";
    //    cout << sortlis[i].x-sortlis[i].prefene << "--\n";
        lisval.insert({sortlis[i].x-sortlis[i].prefene,rootind.back()});
     //   cout << rootind.back() << "\n";
    }
    vector<long long int> lispoc={rootind.back()};
    long long int najv=0;
    for (long long int i=0;i<n;i++){
        long long int pom=lis[i].x;
        pom-=lis[i].prefene;
        pom+=lis[i].ene;
      //  cout << pom << "-\n";
        auto poc=lisval.upper_bound({pom,1e9});
        if (poc==lisval.begin()){
            continue;
        }
        poc=prev(poc);
        long long int poc2=poc->second;
       // cout << poc2 << "\n";
        long long int pom2=que(i,ofs-1,0,ofs-1,poc2,tour);
        pom2--;
       // cout << i << " " << pom2 << "------\n";
        long long int rez=lis[pom2].prefgold;
        if (i>0){
            rez-=lis[i-1].prefgold;
        }
        najv=max(najv,rez);
    }
    cout << najv << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp: In function 'void upd(long long int, long long int, long long int, std::vector<node>&, std::vector<long long int>&, long long int)':
divide.cpp:38:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (long long int i=0;i<indlis.size();i++){
      |                            ~^~~~~~~~~~~~~~
divide.cpp:55:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (long long int i=1;i<indlis2.size();i++){
      |                            ~^~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52