oj.uz

Submission #446349

# Submission time Handle Problem Language Result Execution time Memory
446349 2021-07-21T15:56:37 Z arnold518 Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 973360 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;
const int SQ = 500;

struct Query
{
    int l, r, v;
};

int N, Q;
int A[MAXN+10];
Query B[MAXN+10];
int ans[MAXN+10];

int T1[MAXN+10], T2[MAXN+10];

void calc(int l, int r, vector<Query> B, vector<pii> V2)
{
    //printf("CALC %d %d\n", l, r);
    //for(auto it : B) printf("%d ", it.v); printf("\n");
    //for(int i=l; i<=r; i++) printf("%d ", ans[i]); printf("\n");

    l=max(l, 1); r=min(r, N);
    int Q=B.size();

    vector<ll> V;
    for(int i=0; i<Q; i++)
    {
        if(B[i].v>0)
        {
            ll x=0, y=0;
            while(!V.empty())
            {
                ll x2, y2;
                x2=V.back();
                if(V.size()%2) y2=x2-x+y;
                else y2=y;
                if(y2<x2-B[i].v)
                {
                    V.push_back(y2+B[i].v);
                    break;
                }
                else V.pop_back();
                x=x2; y=y2;
            }
            if(V.empty()) V.push_back(y+B[i].v);
        }
        else
        {
            ll x=0, y=0;
            while(!V.empty())
            {
                ll x2, y2;
                x2=V.back();
                if(V.size()%2) y2=x2-x+y;
                else y2=y;
                if(y2>-B[i].v)
                {
                    V.push_back(x2-y2-B[i].v);
                    break;
                }
                else V.pop_back();
                x=x2; y=y2;
            }
        }
    }

    int pt=0;
    ll x=0, y=0;
    while(!V.empty())
    {
        ll x2, y2;
        x2=V.back();
        if(V.size()%2) y2=x2-x+y;
        else y2=y;

        for(; pt<V2.size() && V2[pt].first<=x2; pt++)
        {
            if(V.size()%2) T1[V2[pt].second]=y2-x2+V2[pt].first;
            else T1[V2[pt].second]=y2;
        }

        V.pop_back();
        x=x2; y=y2;
    }

    for(; pt<V2.size(); pt++)
    {
        T1[V2[pt].second]=y;
    }

    //================================

    for(int i=0; i<Q; i++)
    {
        if(B[i].v>0)
        {
            ll x=0, y=0;
            while(!V.empty())
            {
                ll x2, y2;
                x2=V.back();
                if(V.size()%2) y2=y;
                else y2=x2-x+y;
                if(y2<x2-B[i].v)
                {
                    V.push_back(y2+B[i].v);
                    break;
                }
                else V.pop_back();
                x=x2; y=y2;
            }
        }
        else
        {
            ll x=0, y=0;
            while(!V.empty())
            {
                ll x2, y2;
                x2=V.back();
                if(V.size()%2) y2=y;
                else y2=x2-x+y;
                if(y2>-B[i].v)
                {
                    V.push_back(x2-y2-B[i].v);
                    break;
                }
                else V.pop_back();
                x=x2; y=y2;
            }
            if(V.empty()) V.push_back(-B[i].v-y+x);
        }
    }

    pt=0;
    x=0, y=0;
    while(!V.empty())
    {
        ll x2, y2;
        x2=V.back();
        if(V.size()%2) y2=y;
        else y2=x2-x+y;

        for(; pt<V2.size() && V2[pt].first<=x2; pt++)
        {
            if(V.size()%2) T2[V2[pt].second]=y2;
            else T2[V2[pt].second]=y2-x2+V2[pt].first;
        }

        V.pop_back();
        x=x2; y=y2;
    }
    for(; pt<V2.size(); pt++)
    {
        T2[V2[pt].second]=y-x+V2[pt].first;
    }

    //for(int i=l; i<=r; i++) printf("%d ", T1[i]); printf("T1\n");
    //for(int i=l; i<=r; i++) printf("%d ", T2[i]); printf("T2\n");

    ll t=0;
    for(int i=0; i<Q; i++) t+=B[i].v;

    for(int i=l; i<=r; i++)
    {
        if(T1[i]==T2[i]) ans[i]=T1[i];
        else
        {
            int l=T1[i]-t, r=T2[i]-t;
            if(ans[i]<=l) ans[i]=T1[i];
            else if(ans[i]>=r) ans[i]=T2[i];
            else ans[i]=ans[i]+t;
        }
    }
    //for(int i=l; i<=r; i++) printf("%d ", ans[i]); printf("\n");
}

vector<Query> BB[MAXN+10];

vector<int> distribute_candies(vector<int> _C, vector<int> _L, vector<int> _R, vector<int> _V)
{
    N=_C.size(); Q=_L.size();
    for(int i=1; i<=N; i++) A[i]=_C[i-1];
    for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1, _V[i-1]};

    for(int i=1; i<=Q; i++)
    {
        int l=B[i].l, r=B[i].r, v=B[i].v;
        if(l/SQ==r/SQ)
        {
            BB[l/SQ].push_back({l, r, v});
        }
        else
        {
            BB[l/SQ].push_back({l, min(N, l/SQ*SQ+SQ-1), v});
            BB[r/SQ].push_back({max(1, r/SQ*SQ), r, v});
            for(int j=l/SQ+1; j<r/SQ; j++)
            {
                BB[j].push_back({0, 0, v});
            }
        }
    }
    //printf("HIHI\n");

    for(int i=0; i<=N/SQ; i++)
    {
        int l=max(1, i*SQ), r=min(N, i*SQ+SQ-1);

        vector<pii> V2;
        for(int i=l; i<=r; i++) V2.push_back({A[i], i});
        sort(V2.begin(), V2.end());
        int pt=0;
        vector<Query> V;
        while(pt<BB[i].size())
        {
            for(; pt<BB[i].size() && BB[i][pt].l==0; pt++) V.push_back(BB[i][pt]);
            calc(l, r, V, V2);
            V.clear();
            if(pt<BB[i].size())
            {
                for(int j=BB[i][pt].l; j<=BB[i][pt].r; j++)
                {
                    ans[j]+=BB[i][pt].v;
                    ans[j]=max(ans[j], 0);
                    ans[j]=min(ans[j], A[j]);
                }
                pt++;
            }
        }

    }

    return vector<int>(ans+1, ans+N+1);
}

Compilation message

candies.cpp: In function 'void calc(int, int, std::vector<Query>, std::vector<std::pair<int, int> >)':
candies.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(; pt<V2.size() && V2[pt].first<=x2; pt++)
      |               ~~^~~~~~~~~~
candies.cpp:95:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(; pt<V2.size(); pt++)
      |           ~~^~~~~~~~~~
candies.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(; pt<V2.size() && V2[pt].first<=x2; pt++)
      |               ~~^~~~~~~~~~
candies.cpp:161:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(; pt<V2.size(); pt++)
      |           ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:222:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         while(pt<BB[i].size())
      |               ~~^~~~~~~~~~~~~
candies.cpp:224:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |             for(; pt<BB[i].size() && BB[i][pt].l==0; pt++) V.push_back(BB[i][pt]);
      |                   ~~^~~~~~~~~~~~~
candies.cpp:227:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |             if(pt<BB[i].size())
      |                ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 6 ms 5136 KB Output is correct
5 Correct 24 ms 5260 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2926 ms 352680 KB Output is correct
2 Correct 2968 ms 352608 KB Output is correct
3 Correct 2948 ms 351896 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 1733 ms 21760 KB Output is correct
3 Correct 107 ms 18100 KB Output is correct
4 Correct 3436 ms 352272 KB Output is correct
5 Correct 3535 ms 350868 KB Output is correct
6 Correct 3424 ms 351944 KB Output is correct
7 Correct 3048 ms 351584 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 1232 ms 32028 KB Output is correct
4 Correct 116 ms 21708 KB Output is correct
5 Execution timed out 5153 ms 973360 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 6 ms 5136 KB Output is correct
5 Correct 24 ms 5260 KB Output is correct
6 Correct 2926 ms 352680 KB Output is correct
7 Correct 2968 ms 352608 KB Output is correct
8 Correct 2948 ms 351896 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 1733 ms 21760 KB Output is correct
11 Correct 107 ms 18100 KB Output is correct
12 Correct 3436 ms 352272 KB Output is correct
13 Correct 3535 ms 350868 KB Output is correct
14 Correct 3424 ms 351944 KB Output is correct
15 Correct 3048 ms 351584 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 1232 ms 32028 KB Output is correct
19 Correct 116 ms 21708 KB Output is correct
20 Execution timed out 5153 ms 973360 KB Time limit exceeded
21 Halted 0 ms 0 KB -