oj.uz

Submission #446358

# Submission time Handle Problem Language Result Execution time Memory
446358 2021-07-21T16:28:47 Z arnold518 Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 1074708 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 = 450;

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<int>& 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]>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.push_back(y2+B[i]);
                    break;
                }
                else V.pop_back();
                x=x2; y=y2;
            }
            if(V.empty()) V.push_back(y+B[i]);
        }
        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.push_back(x2-y2-B[i]);
                    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]>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.push_back(y2+B[i]);
                    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.push_back(x2-y2-B[i]);
                    break;
                }
                else V.pop_back();
                x=x2; y=y2;
            }
            if(V.empty()) V.push_back(-B[i]-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];

    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<int> V;
        while(pt<BB[i].size())
        {
            for(; pt<BB[i].size() && BB[i][pt].l==0; pt++) V.push_back(BB[i][pt].v);
            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<int>&, 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].v);
      |                   ~~^~~~~~~~~~~~~
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 3 ms 4940 KB Output is correct
3 Correct 5 ms 5140 KB Output is correct
4 Correct 6 ms 5068 KB Output is correct
5 Correct 19 ms 5240 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2745 ms 386512 KB Output is correct
2 Correct 2671 ms 384040 KB Output is correct
3 Correct 2609 ms 383988 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 1387 ms 20000 KB Output is correct
3 Correct 104 ms 16308 KB Output is correct
4 Correct 3240 ms 386160 KB Output is correct
5 Correct 3201 ms 384016 KB Output is correct
6 Correct 3258 ms 384176 KB Output is correct
7 Correct 2875 ms 385588 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 1343 ms 25688 KB Output is correct
4 Correct 119 ms 21432 KB Output is correct
5 Execution timed out 5162 ms 1074708 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 5 ms 5140 KB Output is correct
4 Correct 6 ms 5068 KB Output is correct
5 Correct 19 ms 5240 KB Output is correct
6 Correct 2745 ms 386512 KB Output is correct
7 Correct 2671 ms 384040 KB Output is correct
8 Correct 2609 ms 383988 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 1387 ms 20000 KB Output is correct
11 Correct 104 ms 16308 KB Output is correct
12 Correct 3240 ms 386160 KB Output is correct
13 Correct 3201 ms 384016 KB Output is correct
14 Correct 3258 ms 384176 KB Output is correct
15 Correct 2875 ms 385588 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 1343 ms 25688 KB Output is correct
19 Correct 119 ms 21432 KB Output is correct
20 Execution timed out 5162 ms 1074708 KB Time limit exceeded
21 Halted 0 ms 0 KB -