oj.uz

Submission #446354

# Submission time Handle Problem Language Result Execution time Memory
446354 2021-07-21T16:25:12 Z arnold518 Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 700136 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#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 = 700;

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:89: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]
   89 |         for(; pt<V2.size() && V2[pt].first<=x2; pt++)
      |               ~~^~~~~~~~~~
candies.cpp:99: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]
   99 |     for(; pt<V2.size(); pt++)
      |           ~~^~~~~~~~~~
candies.cpp:156: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]
  156 |         for(; pt<V2.size() && V2[pt].first<=x2; pt++)
      |               ~~^~~~~~~~~~
candies.cpp:165: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]
  165 |     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:226:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |         while(pt<BB[i].size())
      |               ~~^~~~~~~~~~~~~
candies.cpp:228:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |             for(; pt<BB[i].size() && BB[i][pt].l==0; pt++) V.push_back(BB[i][pt]);
      |                   ~~^~~~~~~~~~~~~
candies.cpp:231:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |             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 4 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 30 ms 5196 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3400 ms 261128 KB Output is correct
2 Correct 3248 ms 259348 KB Output is correct
3 Correct 3223 ms 258060 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 2120 ms 20436 KB Output is correct
3 Correct 106 ms 17024 KB Output is correct
4 Correct 3617 ms 261616 KB Output is correct
5 Correct 3636 ms 261516 KB Output is correct
6 Correct 3700 ms 261304 KB Output is correct
7 Correct 3373 ms 260820 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 2571 ms 26384 KB Output is correct
4 Correct 117 ms 18868 KB Output is correct
5 Execution timed out 5122 ms 700136 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 4 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 30 ms 5196 KB Output is correct
6 Correct 3400 ms 261128 KB Output is correct
7 Correct 3248 ms 259348 KB Output is correct
8 Correct 3223 ms 258060 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 2120 ms 20436 KB Output is correct
11 Correct 106 ms 17024 KB Output is correct
12 Correct 3617 ms 261616 KB Output is correct
13 Correct 3636 ms 261516 KB Output is correct
14 Correct 3700 ms 261304 KB Output is correct
15 Correct 3373 ms 260820 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 2571 ms 26384 KB Output is correct
19 Correct 117 ms 18868 KB Output is correct
20 Execution timed out 5122 ms 700136 KB Time limit exceeded
21 Halted 0 ms 0 KB -