oj.uz

Submission #757624

# Submission time Handle Problem Language Result Execution time Memory
757624 2023-06-13T12:57:07 Z HoriaHaivas Snowball (JOI21_ho_t2) C++14
0 / 100
 1 ms 340 KB 
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int v[200001];
int rightmost[200001];
int leftmost[200001];
int weight[200001];
int w[200001];

bool intervaldone (int query, int pos)
{
     if (rightmost[query]+leftmost[query]>=v[pos+1]-v[pos])
         return 1;
     return 0;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,poz,r,pas;
    cin >> n >> q;
    for (i=1;i<=n;i++)
    {
         cin >> v[i];
    }
    poz=0;
    for (j=1;j<=q;j++)
    {
         cin >> w[j];
         poz+=w[j];
         rightmost[j]=max(rightmost[j-1],poz);
         leftmost[j]=min(leftmost[j-1],poz);
    }
    for (j=1;j<=q;j++)
         leftmost[j]=abs(leftmost[j]);
    weight[1]+=leftmost[q];
    weight[n]+=rightmost[q];
    for (j=1;j<n;j++)
    {
         r=0;
         pas=(1<<17);
         while (pas)
         {
             if (r+pas<=q && !intervaldone(r+pas,j))
                 r+=pas;
             pas=pas/2;
         }
         r++;
         if (rightmost[r]==rightmost[r-1])
         {
             weight[j]+=rightmost[r];
             weight[j+1]+=(v[j+1]-v[j])-rightmost[r];
         }
         else
         {
             weight[j+1]+=leftmost[r];
             weight[j]+=(v[j+1]-v[j])-leftmost[r];
         }
    }
    for (j=1;j<=n;j++)
    {
         cout << weight[j] << "\n";
    }
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -