oj.uz

Submission #446351

# Submission time Handle Problem Language Result Execution time Memory
446351 2021-07-21T16:03:39 Z arnold518 Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 1213832 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 = 400;

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 5068 KB Output is correct
5 Correct 19 ms 5288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2585 ms 435252 KB Output is correct
2 Correct 2532 ms 433608 KB Output is correct
3 Correct 2498 ms 432092 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 1325 ms 21124 KB Output is correct
3 Correct 101 ms 18480 KB Output is correct
4 Correct 3270 ms 436708 KB Output is correct
5 Correct 3293 ms 434964 KB Output is correct
6 Correct 3319 ms 435864 KB Output is correct
7 Correct 2870 ms 436336 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 5000 KB Output is correct
3 Correct 878 ms 33112 KB Output is correct
4 Correct 122 ms 24056 KB Output is correct
5 Execution timed out 5142 ms 1213832 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 5068 KB Output is correct
5 Correct 19 ms 5288 KB Output is correct
6 Correct 2585 ms 435252 KB Output is correct
7 Correct 2532 ms 433608 KB Output is correct
8 Correct 2498 ms 432092 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 1325 ms 21124 KB Output is correct
11 Correct 101 ms 18480 KB Output is correct
12 Correct 3270 ms 436708 KB Output is correct
13 Correct 3293 ms 434964 KB Output is correct
14 Correct 3319 ms 435864 KB Output is correct
15 Correct 2870 ms 436336 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 4 ms 5000 KB Output is correct
18 Correct 878 ms 33112 KB Output is correct
19 Correct 122 ms 24056 KB Output is correct
20 Execution timed out 5142 ms 1213832 KB Time limit exceeded
21 Halted 0 ms 0 KB -