oj.uz

Submission #1046040

# Submission time Handle Problem Language Result Execution time Memory
1046040 2024-08-06T09:18:05 Z ivopav Divide and conquer (IZhO14_divide) C++17
100 / 100
 108 ms 66468 KB 
#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";
}

Compilation message

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 420 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 420 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 820 KB Output is correct
17 Correct 1 ms 1084 KB Output is correct
18 Correct 1 ms 1076 KB Output is correct
19 Correct 1 ms 1044 KB Output is correct
20 Correct 1 ms 1092 KB Output is correct
21 Correct 1 ms 1388 KB Output is correct
22 Correct 2 ms 1400 KB Output is correct
23 Correct 5 ms 4180 KB Output is correct
24 Correct 5 ms 5448 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 420 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 820 KB Output is correct
17 Correct 1 ms 1084 KB Output is correct
18 Correct 1 ms 1076 KB Output is correct
19 Correct 1 ms 1044 KB Output is correct
20 Correct 1 ms 1092 KB Output is correct
21 Correct 1 ms 1388 KB Output is correct
22 Correct 2 ms 1400 KB Output is correct
23 Correct 5 ms 4180 KB Output is correct
24 Correct 5 ms 5448 KB Output is correct
25 Correct 6 ms 4176 KB Output is correct
26 Correct 11 ms 8660 KB Output is correct
27 Correct 9 ms 9924 KB Output is correct
28 Correct 48 ms 33464 KB Output is correct
29 Correct 50 ms 33464 KB Output is correct
30 Correct 108 ms 66468 KB Output is correct
31 Correct 105 ms 66288 KB Output is correct
32 Correct 108 ms 64068 KB Output is correct
33 Correct 107 ms 66064 KB Output is correct
34 Correct 96 ms 65432 KB Output is correct
35 Correct 94 ms 64676 KB Output is correct
36 Correct 96 ms 64232 KB Output is correct