oj.uz

Submission #553590

# Submission time Handle Problem Language Result Execution time Memory
553590 2022-04-26T10:05:57 Z Killer2501 Food Court (JOI21_foodcourt) C++14
24 / 100
 115 ms 48920 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<int, pii>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+2;
const int M = 60;
const int mod = 1e9+7;
const ll base = 1e6;
const ll inf = 1e9;
int n, m, b[N], a[N], k, t, d[N], cnt, par[N];
ll ans, tong;
vector<int> adj[N];
vector<pii> add[N], itadd[N], query[N];
bool vis[N], ok;

struct node
{
    ll sum, suf;
    node()
    {
        sum = 0;
        suf = 0;
    }
    node(ll _sum, ll _suf)
    {
        sum = _sum;
        suf = _suf;
    }
};
node merga(node x, node y)
{
    node res;
    res.sum = x.sum+y.sum;
    res.suf = max(x.suf+y.sum, y.suf);
    return res;
}
struct IT
{
    int n;
    vector<node> st;
    IT(int _n)
    {
        n = _n;
        st.resize(n*4+4);
    }
    void build(int id, int l, int r, int pos, ll x)
    {
        if(l == r)
        {
            st[id] = node(x, x);
            return;
        }
        int mid = (l+r)>>1;
        if(pos <= mid)build(id<<1, l, mid, pos, x);
        else build(id<<1|1, mid+1, r, pos, x);
        st[id] = merga(st[id<<1], st[id<<1|1]);
    }
    void build(int pos, ll x)
    {
        build(1, 1, n, pos, x);
    }
    node get(int id, int l, int r, int u, int v)
    {
        if(u <= l && r <= v)return st[id];
        if(u > r || l > v)return node(0, 0);
        int mid = (l+r)>>1;
        return merga(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
    }
    node get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
};
struct BIT
{
    int n;
    vector<ll> fe;
    BIT(int _n)
    {
        n = _n;
        fe.resize(n+1, 0);
    }
    void add(int id, ll x)
    {
        for(; id <= n; id += id & -id)fe[id] += x;
    }
    ll get(ll id)
    {
        ll total = 0;
        for(; id; id -= id & -id)total += fe[id];
        return total;
    }
    int getK(ll v)
    {
        int pos = 0;
        for(int j = 18; j >= 0; j --)
        {
            pos += (1<<j);
            if(pos <= n && fe[pos] < v)v -= fe[pos];
            else pos -= (1<<j);
        }
        return pos+1;
    }
};
void sol()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i ++)
    {
        a[i] = -1;
        cin >> t;
        if(t == 1)
        {
            int li, ri, ci, ki;
            cin >> li >> ri >> ci >> ki;
            add[li].pb({ki, i});
            add[ri+1].pb({-ki, i});
            itadd[li].pb({ki, i});
            itadd[ri+1].pb({0, i});
            d[i] = ci;
        }
        else if(t == 2)
        {
            int li, ri, ki;
            cin >> li >> ri >> ki;
            itadd[li].pb({-ki, i});
            itadd[ri+1].pb({0, i});
        }
        else
        {
            int li, ki;
            cin >> li >> ki;
            query[li].pb({ki, i});
        }
    }
    IT it(k);
    BIT bit(k);
    for(int i = 1; i <= n; i ++)
    {
        for(pii x: add[i])bit.add(x.se, x.fi);
        for(pii x: itadd[i])
        {
            //cout << x.se <<" "<<x.fi<<" "<<i<<'\n';
            it.build(x.se, x.fi);
        }
        for(pii x: query[i])
        {
            ans = it.get(1, x.se).suf;
            b[x.se] = bit.get(x.se)-ans+x.fi;
            if(ans < x.fi)a[x.se] = 0;
            else a[x.se] = d[bit.getK(bit.get(x.se)-(ans-x.fi))];
        }
    }
    for(int i = 1; i <= k; i ++)if(a[i] != -1)cout << a[i]<<'\n';
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
2 1 6 5 4 3
*/

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:170:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:171:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 14 ms 28744 KB Output is correct
3 Correct 15 ms 28656 KB Output is correct
4 Correct 17 ms 28884 KB Output is correct
5 Correct 14 ms 28644 KB Output is correct
6 Correct 15 ms 28716 KB Output is correct
7 Correct 15 ms 28748 KB Output is correct
8 Correct 16 ms 28756 KB Output is correct
9 Correct 21 ms 28756 KB Output is correct
10 Correct 19 ms 28764 KB Output is correct
11 Correct 16 ms 28748 KB Output is correct
12 Correct 17 ms 28756 KB Output is correct
13 Correct 15 ms 28756 KB Output is correct
14 Correct 15 ms 28700 KB Output is correct
15 Correct 15 ms 28608 KB Output is correct
16 Correct 18 ms 28748 KB Output is correct
17 Correct 16 ms 28748 KB Output is correct
18 Correct 15 ms 28788 KB Output is correct
19 Correct 16 ms 28784 KB Output is correct
20 Correct 16 ms 28784 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 14 ms 28744 KB Output is correct
3 Correct 15 ms 28656 KB Output is correct
4 Correct 17 ms 28884 KB Output is correct
5 Correct 14 ms 28644 KB Output is correct
6 Correct 15 ms 28716 KB Output is correct
7 Correct 15 ms 28748 KB Output is correct
8 Correct 16 ms 28756 KB Output is correct
9 Correct 21 ms 28756 KB Output is correct
10 Correct 19 ms 28764 KB Output is correct
11 Correct 16 ms 28748 KB Output is correct
12 Correct 17 ms 28756 KB Output is correct
13 Correct 15 ms 28756 KB Output is correct
14 Correct 15 ms 28700 KB Output is correct
15 Correct 15 ms 28608 KB Output is correct
16 Correct 18 ms 28748 KB Output is correct
17 Correct 16 ms 28748 KB Output is correct
18 Correct 15 ms 28788 KB Output is correct
19 Correct 16 ms 28784 KB Output is correct
20 Correct 16 ms 28784 KB Output is correct
21 Incorrect 14 ms 28756 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 38260 KB Output is correct
2 Correct 96 ms 38720 KB Output is correct
3 Correct 76 ms 38476 KB Output is correct
4 Correct 74 ms 38304 KB Output is correct
5 Correct 90 ms 38788 KB Output is correct
6 Correct 101 ms 38812 KB Output is correct
7 Correct 40 ms 35516 KB Output is correct
8 Correct 42 ms 35588 KB Output is correct
9 Correct 84 ms 38332 KB Output is correct
10 Correct 85 ms 38448 KB Output is correct
11 Correct 115 ms 38396 KB Output is correct
12 Correct 109 ms 38540 KB Output is correct
13 Correct 70 ms 37396 KB Output is correct
14 Correct 78 ms 38744 KB Output is correct
15 Correct 102 ms 38808 KB Output is correct
16 Correct 113 ms 39328 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 48920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 14 ms 28744 KB Output is correct
3 Correct 15 ms 28656 KB Output is correct
4 Correct 17 ms 28884 KB Output is correct
5 Correct 14 ms 28644 KB Output is correct
6 Correct 15 ms 28716 KB Output is correct
7 Correct 15 ms 28748 KB Output is correct
8 Correct 16 ms 28756 KB Output is correct
9 Correct 21 ms 28756 KB Output is correct
10 Correct 19 ms 28764 KB Output is correct
11 Correct 16 ms 28748 KB Output is correct
12 Correct 17 ms 28756 KB Output is correct
13 Correct 15 ms 28756 KB Output is correct
14 Correct 15 ms 28700 KB Output is correct
15 Correct 15 ms 28608 KB Output is correct
16 Correct 18 ms 28748 KB Output is correct
17 Correct 16 ms 28748 KB Output is correct
18 Correct 15 ms 28788 KB Output is correct
19 Correct 16 ms 28784 KB Output is correct
20 Correct 16 ms 28784 KB Output is correct
21 Correct 99 ms 38260 KB Output is correct
22 Correct 96 ms 38720 KB Output is correct
23 Correct 76 ms 38476 KB Output is correct
24 Correct 74 ms 38304 KB Output is correct
25 Correct 90 ms 38788 KB Output is correct
26 Correct 101 ms 38812 KB Output is correct
27 Correct 40 ms 35516 KB Output is correct
28 Correct 42 ms 35588 KB Output is correct
29 Correct 84 ms 38332 KB Output is correct
30 Correct 85 ms 38448 KB Output is correct
31 Correct 115 ms 38396 KB Output is correct
32 Correct 109 ms 38540 KB Output is correct
33 Correct 70 ms 37396 KB Output is correct
34 Correct 78 ms 38744 KB Output is correct
35 Correct 102 ms 38808 KB Output is correct
36 Correct 113 ms 39328 KB Output is correct
37 Correct 73 ms 37176 KB Output is correct
38 Correct 77 ms 36696 KB Output is correct
39 Correct 41 ms 34600 KB Output is correct
40 Correct 45 ms 35676 KB Output is correct
41 Correct 86 ms 38248 KB Output is correct
42 Correct 87 ms 38312 KB Output is correct
43 Correct 99 ms 38280 KB Output is correct
44 Correct 92 ms 38232 KB Output is correct
45 Correct 80 ms 38348 KB Output is correct
46 Correct 84 ms 38276 KB Output is correct
47 Correct 53 ms 36512 KB Output is correct
48 Correct 69 ms 37196 KB Output is correct
49 Correct 58 ms 35432 KB Output is correct
50 Correct 68 ms 36948 KB Output is correct
51 Correct 85 ms 38372 KB Output is correct
52 Correct 89 ms 38360 KB Output is correct
53 Correct 80 ms 37004 KB Output is correct
54 Correct 83 ms 39324 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 34044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 14 ms 28744 KB Output is correct
3 Correct 15 ms 28656 KB Output is correct
4 Correct 17 ms 28884 KB Output is correct
5 Correct 14 ms 28644 KB Output is correct
6 Correct 15 ms 28716 KB Output is correct
7 Correct 15 ms 28748 KB Output is correct
8 Correct 16 ms 28756 KB Output is correct
9 Correct 21 ms 28756 KB Output is correct
10 Correct 19 ms 28764 KB Output is correct
11 Correct 16 ms 28748 KB Output is correct
12 Correct 17 ms 28756 KB Output is correct
13 Correct 15 ms 28756 KB Output is correct
14 Correct 15 ms 28700 KB Output is correct
15 Correct 15 ms 28608 KB Output is correct
16 Correct 18 ms 28748 KB Output is correct
17 Correct 16 ms 28748 KB Output is correct
18 Correct 15 ms 28788 KB Output is correct
19 Correct 16 ms 28784 KB Output is correct
20 Correct 16 ms 28784 KB Output is correct
21 Incorrect 14 ms 28756 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 14 ms 28744 KB Output is correct
3 Correct 15 ms 28656 KB Output is correct
4 Correct 17 ms 28884 KB Output is correct
5 Correct 14 ms 28644 KB Output is correct
6 Correct 15 ms 28716 KB Output is correct
7 Correct 15 ms 28748 KB Output is correct
8 Correct 16 ms 28756 KB Output is correct
9 Correct 21 ms 28756 KB Output is correct
10 Correct 19 ms 28764 KB Output is correct
11 Correct 16 ms 28748 KB Output is correct
12 Correct 17 ms 28756 KB Output is correct
13 Correct 15 ms 28756 KB Output is correct
14 Correct 15 ms 28700 KB Output is correct
15 Correct 15 ms 28608 KB Output is correct
16 Correct 18 ms 28748 KB Output is correct
17 Correct 16 ms 28748 KB Output is correct
18 Correct 15 ms 28788 KB Output is correct
19 Correct 16 ms 28784 KB Output is correct
20 Correct 16 ms 28784 KB Output is correct
21 Incorrect 14 ms 28756 KB Output isn't correct
22 Halted 0 ms 0 KB -