oj.uz

Submission #724079

# Submission time Handle Problem Language Result Execution time Memory
724079 2023-04-14T17:04:18 Z Quentolosse Measures (CEOI22_measures) C++14
0 / 100
 1500 ms 31536 KB 
#include <bits/stdc++.h>
    
#define int long long
    
using namespace std;
    
const int inf = 1e9;
    
struct node
{
    int maxi = -inf, mini = inf, reponse = -inf, decalage = 0;
};

vector<node> segtree;
int n, m, d;

node merge (node a, node b)
{
    node c;
    c.maxi = max(a.maxi + a.decalage, b.maxi + b.decalage);
    c.mini = min(a.mini + a.decalage, b.mini + b.decalage);
    c.reponse = max(a.maxi - b.mini, max(a.reponse, b.reponse));
    return c;
}

void update (int i, node a)
{
    segtree[i] = a;
    if (i == 1)
    {
        return;
    }
    if (i % 2)
    {
        update((i - 1) / 2, merge(segtree[i - 1], segtree[i]));
    }
    else
    {
        update(i / 2, merge(segtree[i], segtree[i + 1]));
    }
}

void decalage (int i, int L, int l, int r, int R)
{
    if (L == l && r == R)
    {
        node a = segtree[i];
        a.decalage = -d;
        update(i, a);
        return;
    }
    if (l < (L + R) / 2)
        decalage(i * 2, L, l, min(r, R), (L + R) / 2);
    if (r > (L + R) / 2)
        decalage(i * 2 + 1, (L + R) / 2, max(l, L), r, R);

}

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    
    cin >> n >> m >> d;
    
    segtree.resize(4 * (n + m) + 5);
    vector<int> debut (n);
    
    for (int i = 0; i < n; i++)
    {
        cin >> debut[i];
    }


    vector<int> requetes (m);
    
    for (int i = 0; i < m; i++)
    {
        cin >> requetes[i];
    }
    
    vector<pair<int, int>> points (n + m);


    for (int i = 0; i < n; i++)
    {
        points[i].first = debut[i];
        points[i].second = i;
    }
    
    for (int i = 0; i < m; i ++)
    {
        points[n + i].first = requetes[i];
        points[n + i].second = n + i;
    }

   

    sort(points.begin(), points.end());
    
    vector<int> posRequete (m);
     
    for (int i = 0; i < n + m; i++)
    {
        if (points[i].second < n)
        {
            node a;
            a.maxi = points[i].first;
            a.mini = points[i].first;
            update(n + m + 1, a);
        } 
        else
        {
            posRequete[points[i].second] = i;
        }
    }

    

    for (int i = 0; i < m; i++)
    {

        int pos = posRequete[i];
        node a;
        a.maxi = points[pos].first;
        a.mini = points[pos].first;

        decalage(1, 0, pos + 1, n + m, n + m);

        update(n + m + i + pos, a);
        
        int reponse = segtree[1].reponse;

        cout << reponse / 2;
        if (reponse % 2) cout << ".5";
        cout << ' ';

    }
    
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 31536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 31536 KB Time limit exceeded
2 Halted 0 ms 0 KB -