oj.uz

답안 #885488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
885488 2023-12-09T20:30:07 Z vjudge1 Foehn Phenomena (JOI17_foehn_phenomena) C++17
30 / 100
 1000 ms 12080 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

int ans = 0, n, q, s, t; 

int f(int a, int b)
{
    if(a < b)
        return (a - b) * s; 
    else 
        return (a - b) * t; 
}

struct SQRT
{
    vector <int> block, sec; int sqrt_n;

    void update(int l, int r, int v)
    {
        ans -= f(block[((l - 1) / sqrt_n)] + sec[l - 1], block[((l) / sqrt_n)] + sec[l]); 
        if(r != n) ans -= f(block[((r) / sqrt_n)] + sec[r], block[((r + 1) / sqrt_n)] + sec[r + 1]); 

        for(int i = l; i <= r; i++)
        {
            if((i % sqrt_n == 0) && (i + sqrt_n <= r))
                block[(i / sqrt_n)] += v, i += sqrt_n - 1;
            else
                sec[i] += v;
        }

        ans += f(block[((l - 1) / sqrt_n)] + sec[l - 1], block[((l) / sqrt_n)] + sec[l]); 
        if(r != n) ans += f(block[((r) / sqrt_n)] + sec[r], block[((r + 1) / sqrt_n)] + sec[r + 1]); 
    }

    SQRT(int n)
    {
        sqrt_n = sqrt(n) + 1;
        block.assign(sqrt_n + 7, 0);
        sec.assign(n + 7, 0);
    }
};

void solve()
{
    cin >> n >> q >> s >> t; 
    vector <int> v(n+1); 
    for(auto& u : v) cin >> u; 

    SQRT St(n+7);
    for(int i = 1; i <= n; i++)
        St.update(i, i, v[i]);
    
    while (q--)
    {
        int l, r, x; cin >> l >> r >> x; 
        St.update(l, r, x); 
        cout << ans << endl; 
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 532 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 3 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 736 ms 10320 KB Output is correct
2 Correct 734 ms 11344 KB Output is correct
3 Correct 735 ms 11632 KB Output is correct
4 Correct 729 ms 11224 KB Output is correct
5 Correct 733 ms 12080 KB Output is correct
6 Execution timed out 1056 ms 10852 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 532 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 3 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 736 ms 10320 KB Output is correct
23 Correct 734 ms 11344 KB Output is correct
24 Correct 735 ms 11632 KB Output is correct
25 Correct 729 ms 11224 KB Output is correct
26 Correct 733 ms 12080 KB Output is correct
27 Execution timed out 1056 ms 10852 KB Time limit exceeded
28 Halted 0 ms 0 KB -