Submission #519528

#	Time	Username	Problem	Language	Result	Execution time	Memory
519528		Andrei_Cotor	Divide and conquer (IZhO14_divide)	C++17	100 / 100	59 ms	8928 KiB

divide

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

using namespace std;

struct Mine
{
    int position, energy, gold;
};

vector<long long> PosibleIndexes;

int normalize(long long index)
{
    int rez=0;
    for(int i=20; i>=0; i--)
    {
        if((rez^(1<<i))<PosibleIndexes.size() && PosibleIndexes[rez^(1<<i)]<=index)
        {
            rez^=(1<<i);
        }
    }

    return rez+1;
}

void create_normalization(int n, Mine Mines[], long long SumEnergy[])
{
    for(int i=1; i<=n; i++)
    {
        PosibleIndexes.push_back(1LL*Mines[i].position-SumEnergy[i-1]);
        PosibleIndexes.push_back(1LL*Mines[i].position-SumEnergy[i]);
    }

    sort(PosibleIndexes.begin(), PosibleIndexes.end());
}

class FenwickTree
{
private:
    int F[200005];
    int MAX_FENWICK;
public:

    FenwickTree(int sz)
    {
        MAX_FENWICK=sz;
        for(int i=1; i<=MAX_FENWICK; i++)
        {
            F[i]=100001;
        }
    }

    void update(long long pos, int val)
    {
        pos=normalize(pos);

        while(pos>0)
        {
            F[pos]=min(F[pos],val);
            pos=pos-(pos&(pos^(pos-1)));
        }
    }

    int query(long long pos)
    {
        pos=normalize(pos);

        int rez=100001;
        while(pos<=MAX_FENWICK)
        {
            rez=min(rez,F[pos]);
            pos=pos+(pos&(pos^(pos-1)));
        }
        return rez;
    }
};

Mine Mines[100005];
long long SumEnergy[100005];
long long SumGold[100005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        cin>>Mines[i].position>>Mines[i].gold>>Mines[i].energy;
    }

    for(int i=1; i<=n; i++)
    {
        SumEnergy[i]=SumEnergy[i-1]+Mines[i].energy;
        SumGold[i]=SumGold[i-1]+Mines[i].gold;
    }

    create_normalization(n, Mines, SumEnergy);
    FenwickTree FT=FenwickTree(2*n);

    long long rez=0;
    for(int i=1; i<=n; i++)
    {
        FT.update(1LL*Mines[i].position-SumEnergy[i-1],i);

        int bestLeft=FT.query(1LL*Mines[i].position-SumEnergy[i]);
        rez=max(rez,SumGold[i]-SumGold[bestLeft-1]);
    }

    cout<<rez<<"\n";
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int normalize(long long int)':
divide.cpp:19:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if((rez^(1<<i))<PosibleIndexes.size() && PosibleIndexes[rez^(1<<i)]<=index)
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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