oj.uz

Submission #314257

# Submission time Handle Problem Language Result Execution time Memory
314257 2020-10-19T09:13:49 Z Trickster Trading (IZhO13_trading) C++14
100 / 100
 730 ms 10872 KB 
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define N 300010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n, q;
int v[N];
int L[N*4];

void shift(int x, int to)
{
    L[to] = max(x, L[to]);
}

void upd(int a, int b, int x, int l, int r, int node)
{
    if(l > b || r < a) return;

    if(l >= a && r <= b) {
        // cout << l << " " << r << " " << x+l-a << "\n";

        L[node] = max(x+l-a, L[node]);
        return;
    }

    if(L[node]) {
        shift(L[node], node*2);
        shift(L[node]+(l+r)/2-l+1, node*2+1);
        L[node] = 0;
    }

    upd(a, b, x, l, (l+r)/2, node*2);
    upd(a, b, x, (l+r)/2+1, r, node*2+1);
}
int tap(int pos, int l, int r, int node)
{
    if(l == r) return L[node];

    if(L[node]) {
        shift(L[node], node*2);
        shift(L[node]+(l+r)/2-l+1, node*2+1);
        L[node] = 0;
    }

    if(pos <= (l+r)/2)
        return tap(pos, l, (l+r)/2, node*2);
    else
        return tap(pos, (l+r)/2+1, r, node*2+1);
}

int main()
{
    cin >> n >> q;

    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;

        upd(l, r, x, 1, n, 1);
    }

    for(int i = 1; i <= n; i++) cout << tap(i, 1, n, 1) << " ";
}
/*
5 2
1 3 2
2 4 6

6 4
4 4 3
1 2 5
5 6 1
6 6 1
*/

Compilation message

trading.cpp:22: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   22 | #pragma GCC optimization ("O3")
      | 
trading.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 356 ms 5528 KB Output is correct
8 Correct 390 ms 6392 KB Output is correct
9 Correct 422 ms 6236 KB Output is correct
10 Correct 440 ms 5624 KB Output is correct
11 Correct 453 ms 7420 KB Output is correct
12 Correct 504 ms 6904 KB Output is correct
13 Correct 513 ms 7484 KB Output is correct
14 Correct 533 ms 6748 KB Output is correct
15 Correct 584 ms 7800 KB Output is correct
16 Correct 609 ms 8184 KB Output is correct
17 Correct 593 ms 9036 KB Output is correct
18 Correct 636 ms 10060 KB Output is correct
19 Correct 624 ms 8984 KB Output is correct
20 Correct 730 ms 10872 KB Output is correct