oj.uz

Submission #519527

# Submission time Handle Problem Language Result Execution time Memory
519527 2022-01-26T14:21:01 Z Andrei_Cotor Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 972 KB 
#include<fstream>
#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()
{
    ifstream fi("divide.in");
    ofstream fo("divide.out");

    int n;
    fi>>n;

    for(int i=1; i<=n; i++)
    {
        fi>>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]);
    }

    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 972 KB Output isn't correct
2 Halted 0 ms 0 KB -