oj.uz

Submission #437822

# Submission time Handle Problem Language Result Execution time Memory
437822 2021-06-27T07:25:09 Z ymm Distributing Candies (IOI21_candies) C++17
100 / 100
 4675 ms 14568 KB 
///
///    "Excuse me... What did you say about my hair?!"
///
///                                    -Josuke Higashikata

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx")
typedef vector<int> vec;

const int N = 200'010;
int a[N], c[N], l[N], r[N], v[N];
int n, q;

vec distribute_candies(vec cc, vec ll, vec rr, vec vv)
{
    n = cc.size();
    q = ll.size();
    while(q%2)
    {
        ++q;
        ll.push_back(0);
        rr.push_back(1);
        vv.push_back(0);
    }
    Loop(i,0,n) c[i] = cc[i];
    Loop(i,0,q) l[i] = ll[i], r[i] = rr[i], v[i] = vv[i];
    for(int i=0;i<q;i+=2)
    {
        int v0=v[i+0], l0=l[i+0], r0=r[i+0]+1;
        int v1=v[i+1], l1=l[i+1], r1=r[i+1]+1;
        if(false){}
        else if(l0<=r0&&r0<=l1&&l1<=r1&&1){
                if(v0<=0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1<=0) for(int j=r0;j<l1;++j) {}
                if(v0>0 && v1<=0) for(int j=r0;j<l1;++j) {}
                if(v0<=0 && v1>0) for(int j=r0;j<l1;++j) {}
                if(v0>0 && v1>0) for(int j=r0;j<l1;++j) {}
                if(v0<=0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
        }
        else if(l0<=l1&&l1<=r0&&r0<=r1&&1){
                if(v0<=0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1<=0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
        }
        else if(l0<=l1&&l1<=r1&&r1<=r0&&1){
                if(v0<=0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
        }
        else if(l1<=l0&&l0<=r0&&r0<=r1&&1){
                if(v0<=0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
        }
        else if(l1<=l0&&l0<=r1&&r1<=r0&&1){
                if(v0<=0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
        }
        else if(l1<=r1&&r1<=l0&&l0<=r0&&1){
                if(v0<=0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r1;j<l0;++j) {}
                if(v0>0 && v1<=0) for(int j=r1;j<l0;++j) {}
                if(v0<=0 && v1>0) for(int j=r1;j<l0;++j) {}
                if(v0>0 && v1>0) for(int j=r1;j<l0;++j) {}
                if(v0<=0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
        }
    }
    vec ans(n);
    Loop(i,0,n) ans[i] = a[i];
    return ans;
}

/*int main()
{
    //auto ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
    //for(int x : ans) cout << x << ' ';
    vec c(200000, 1e9);
    vec l(200000, 0);
    vec r(200000, 199999);
    vec v(200000, 12);
    distribute_candies(c,l,r,v);
    /*printf("int v0=v[i+0], l0=l[i+0], r0=r[i+0]+1;\n");
    printf("int v1=v[i+1], l1=l[i+1], r1=r[i+1]+1;\n");
    printf("if(false){}\n");
    int p[4] = {0, 0, 1, 1};
    do
    {
        int a = 0;
        printf("else if(");
        Loop(i,0,4-1)
        {
            printf("%c%d",a&(1<<p[i])?'r':'l',p[i]);
            a ^= (1<<p[i]);
            printf("<=%c%d&&",a&(1<<p[i+1])?'r':'l',p[i+1]);
        }
        printf("1){\n");
        a = 0;
        Loop(i,0,4-1)
        {
            Loop(k,0,4)
            {
                printf("\tif(%s && %s) ", k&1? "v0>0": "v0<=0", k&2? "v1>0": "v1<=0");
                printf("for(int j=%c%d;",a&(1<<p[i])?'r':'l',p[i]);
                a ^= (1<<p[i]);
                printf("j<%c%d;++j) {",a&(1<<p[i+1])?'r':'l',p[i+1]);
                Loop(j,0,2)
                    if(a&(1<<j)){
                        if(k&(1<<j))
                            printf("a[j]=a[j]+v%d>c[j]?c[j]:a[j]+v%d;",j,j);
                        else
                            printf("a[j]=a[j]+v%d<0?0:a[j]+v%d;",j,j);
                    }
                printf("}\n");
                a ^= (1<<p[i]);
            }
            a ^= (1<<p[i]);
        }
        printf("}\n");
    }while(next_permutation(p, p+4));
}*/

Compilation message

candies.cpp:147:5: warning: "/*" within comment [-Wcomment]
  147 |     /*printf("int v0=v[i+0], l0=l[i+0], r0=r[i+0]+1;\n");
      |

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2680 ms 11248 KB Output is correct
2 Correct 2655 ms 11248 KB Output is correct
3 Correct 2708 ms 11244 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 96 ms 7388 KB Output is correct
3 Correct 86 ms 5424 KB Output is correct
4 Correct 2670 ms 11244 KB Output is correct
5 Correct 2600 ms 11244 KB Output is correct
6 Correct 2596 ms 11252 KB Output is correct
7 Correct 2728 ms 11240 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 97 ms 7272 KB Output is correct
4 Correct 100 ms 4348 KB Output is correct
5 Correct 4433 ms 11252 KB Output is correct
6 Correct 4480 ms 13792 KB Output is correct
7 Correct 4386 ms 13772 KB Output is correct
8 Correct 4547 ms 13788 KB Output is correct
9 Correct 4675 ms 13660 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2680 ms 11248 KB Output is correct
7 Correct 2655 ms 11248 KB Output is correct
8 Correct 2708 ms 11244 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 96 ms 7388 KB Output is correct
11 Correct 86 ms 5424 KB Output is correct
12 Correct 2670 ms 11244 KB Output is correct
13 Correct 2600 ms 11244 KB Output is correct
14 Correct 2596 ms 11252 KB Output is correct
15 Correct 2728 ms 11240 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 97 ms 7272 KB Output is correct
19 Correct 100 ms 4348 KB Output is correct
20 Correct 4433 ms 11252 KB Output is correct
21 Correct 4480 ms 13792 KB Output is correct
22 Correct 4386 ms 13772 KB Output is correct
23 Correct 4547 ms 13788 KB Output is correct
24 Correct 4675 ms 13660 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 85 ms 5476 KB Output is correct
27 Correct 96 ms 9944 KB Output is correct
28 Correct 2568 ms 14028 KB Output is correct
29 Correct 2551 ms 14560 KB Output is correct
30 Correct 2540 ms 14556 KB Output is correct
31 Correct 2646 ms 14560 KB Output is correct
32 Correct 2679 ms 14568 KB Output is correct