oj.uz

Submission #525953

# Submission time Handle Problem Language Result Execution time Memory
525953 2022-02-13T09:54:25 Z ivan_tudor Food Court (JOI21_foodcourt) C++14
24 / 100
 177 ms 29476 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 250005;
struct ainthelp{
  long long lazy;
  long long minv;
  int minp;
};
ainthelp aint[4*N];
void propag(int nod, int l, int r){
  aint[nod].minv += aint[nod].lazy;
  if(l != r){
    aint[2*nod].lazy += aint[nod].lazy;
    aint[2*nod + 1].lazy += aint[nod].lazy;
  }
  aint[nod].lazy = 0;
}
ainthelp join(ainthelp a, ainthelp b){
  ainthelp rsp;
  rsp.lazy = 0;
  if(a.minv < b.minv){
    rsp.minv = a.minv;
    rsp.minp = a.minp;
  }
  else if(b.minv < a.minv){
    rsp.minv = b.minv;
    rsp.minp = b.minp;
  }
  else if(a.minv == b.minv){
    rsp.minv = a.minv;
    rsp.minp = max(a.minp, b.minp);
  }
  return rsp;
}
void aint_build(int nod, int l, int r){
  if(l == r){
    aint[nod].lazy = aint[nod].minv = 0;
    aint[nod].minp = l;
    return;
  }
  int mid = (l +r)/2;
  aint_build(2*nod, l, mid);
  aint_build(2*nod + 1, mid + 1, r);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
void update(int nod, int l, int r, int ul, int ur, long long val){
  propag(nod, l, r);
  if(r < ul || ur < l)
    return;
  if(ul <= l && r <= ur){
    aint[nod].lazy += val;
    propag(nod, l, r);
    return;
  }
  int mid = (l +r)/2;
  update(2*nod, l, mid, ul, ur, val);
  update(2*nod + 1, mid + 1, r, ul, ur, val);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
long long querypoz(int nod, int l, int r, int poz){
  propag(nod, l, r);
  if(poz < l || poz > r)
    return LLONG_MIN;
  if(l == r)
    return aint[nod].minv;
  int mid = (l + r)/2;
  long long ls = querypoz(2*nod, l, mid, poz);
  long long dr = querypoz(2*nod + 1, mid + 1, r, poz);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
  return max(ls, dr);
}
ainthelp queryitv(int nod, int l, int r, int ql, int qr){
  propag(nod, l, r);
  if(r < ql || l > qr)
    return {0, LLONG_MAX, INT_MAX};
  if(ql <= l && r <= qr)
    return aint[nod];
  int mid = (l +r)/2;
  ainthelp left = queryitv(2*nod, l, mid, ql, qr);
  ainthelp right = queryitv(2*nod + 1, mid + 1, r, ql, qr);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
  return join(left, right);
}
long long aibpoz[N];
void aib_upd(int poz, long long val){
  for(int i = poz; i < N; i += i&(-i))
    aibpoz[i] += val;
}
long long aib_query(int poz){
  long long rsp = 0;
  for(int i = poz; i >0; i-= i&(-i)){
    rsp += aibpoz[i];
  }
  return rsp;
}
int aib_bs(long long val){ /// first >= val
  int pas = 0;
  for(int p2 = 1<<20; p2>0; p2>>=1){
    if(pas + p2 < N && aibpoz[pas + p2] < val){
      pas += p2;
      val -= aibpoz[pas];
    }
  }
  return pas + 1;
}
struct updates{
  int val; /// val > 0, group > 0 => type 1; val < 0 => type = 2
  int group;
};
updates tme[N];
struct smenhelper{
  int type; /// add(1), erase(-1)
  int time;
  updates upd;

};

vector<smenhelper> smen[N];
vector<smenhelper> queries[N];
int answers[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m, q;
  cin>>n>>m>>q;
  for(int i = 1; i <=q; i++){
    answers[i] = -1;
    int t;
    cin>>t;
    if(t == 1){
      int l, r, val, gr;
      cin>>l>>r>>gr>>val;
      smenhelper addval{1, i, {val, gr}};
      smen[l].push_back(addval);

      smenhelper delval{-1, i, {val, gr}};
      smen[r + 1].push_back(delval);
    }
    else if(t == 2){
      int l, r, val;
      cin>>l>>r>>val;
      smenhelper addval{1, i, {-val, 0}};
      smen[l].push_back(addval);

      smenhelper delval{-1, i, {-val, 0}};
      smen[r + 1].push_back(delval);
    }
    else if(t == 3){
      int poz, val;
      cin>>poz>>val;
      smenhelper qry{0, i, {val, 0}};
      queries[poz].push_back(qry);
    }
  }
  ///aint size = q ( TMAX = q)
  /// aint de la 0 la q
  aint_build(1, 0, q);
  for(int i = 1; i<=n; i++){
    for(auto change:smen[i]){
      if(change.type == 1){ ///insert new update
        updates upd = change.upd;
        tme[change.time] = upd;
        if(upd.val > 0){ /// type = 1 => new members in queues
          update(1, 0, q, change.time, q, 1LL*upd.val);
          aib_upd(change.time, 1LL * upd.val);
        }
        else if(upd.val < 0){ /// type = 2 => leave from queue
          update(1, 0, q, change.time, q, 1LL * upd.val);
        }
      }
      else if(change.type == -1){ /// delete old update
        updates upd = change.upd;
        tme[change.time] = {0, 0};
        if(upd.val > 0){ ///type = 1 => have to remove old members
          update(1, 0, q, change.time, q, -1LL * upd.val);
          aib_upd(change.time, -1LL * upd.val);
        }
        else if(upd.val <0){ ///type = 2 => have to add them back
            update(1, 0, q, change.time, q, -1LL * upd.val);
        }
      }
    }
    for(auto qry:queries[i]){
      int time = qry.time;
      long long val = qry.upd.val;

      ainthelp minq = queryitv(1, 0, q, 0, time);
      long long minval = minq.minv;
      long long lastval = querypoz(1, 0, q, time);
      long long cval = lastval - minval;
      if(val > cval){
        answers[time] = 0;
      }
      else{
        long long alladded = aib_query(time);
        long long lookingfor = alladded - (cval - val);
        int id = aib_bs(lookingfor);
        answers[time] = tme[id].group;
      }
    }
  }
  for(int i = 1; i <=q; i++){
    if(answers[i] != -1)
      cout<<answers[i]<<"\n";
  }
  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12236 KB Output is correct
2 Correct 9 ms 12364 KB Output is correct
3 Correct 8 ms 12228 KB Output is correct
4 Correct 9 ms 12240 KB Output is correct
5 Correct 7 ms 12364 KB Output is correct
6 Correct 7 ms 12336 KB Output is correct
7 Correct 10 ms 12340 KB Output is correct
8 Correct 8 ms 12348 KB Output is correct
9 Correct 8 ms 12364 KB Output is correct
10 Correct 9 ms 12340 KB Output is correct
11 Correct 8 ms 12340 KB Output is correct
12 Correct 8 ms 12364 KB Output is correct
13 Correct 7 ms 12340 KB Output is correct
14 Correct 8 ms 12364 KB Output is correct
15 Correct 8 ms 12236 KB Output is correct
16 Correct 8 ms 12388 KB Output is correct
17 Correct 8 ms 12232 KB Output is correct
18 Correct 8 ms 12256 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 8 ms 12364 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12236 KB Output is correct
2 Correct 9 ms 12364 KB Output is correct
3 Correct 8 ms 12228 KB Output is correct
4 Correct 9 ms 12240 KB Output is correct
5 Correct 7 ms 12364 KB Output is correct
6 Correct 7 ms 12336 KB Output is correct
7 Correct 10 ms 12340 KB Output is correct
8 Correct 8 ms 12348 KB Output is correct
9 Correct 8 ms 12364 KB Output is correct
10 Correct 9 ms 12340 KB Output is correct
11 Correct 8 ms 12340 KB Output is correct
12 Correct 8 ms 12364 KB Output is correct
13 Correct 7 ms 12340 KB Output is correct
14 Correct 8 ms 12364 KB Output is correct
15 Correct 8 ms 12236 KB Output is correct
16 Correct 8 ms 12388 KB Output is correct
17 Correct 8 ms 12232 KB Output is correct
18 Correct 8 ms 12256 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 8 ms 12364 KB Output is correct
21 Incorrect 7 ms 12328 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 92 ms 20420 KB Output is correct
2 Correct 92 ms 20676 KB Output is correct
3 Correct 92 ms 20416 KB Output is correct
4 Correct 89 ms 20460 KB Output is correct
5 Correct 114 ms 20776 KB Output is correct
6 Correct 94 ms 20656 KB Output is correct
7 Correct 53 ms 18752 KB Output is correct
8 Correct 52 ms 19100 KB Output is correct
9 Correct 88 ms 20452 KB Output is correct
10 Correct 91 ms 20684 KB Output is correct
11 Correct 90 ms 20552 KB Output is correct
12 Correct 90 ms 20636 KB Output is correct
13 Correct 83 ms 19756 KB Output is correct
14 Correct 91 ms 20436 KB Output is correct
15 Correct 95 ms 20788 KB Output is correct
16 Correct 92 ms 20804 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 29476 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 7 ms 12236 KB Output is correct
2 Correct 9 ms 12364 KB Output is correct
3 Correct 8 ms 12228 KB Output is correct
4 Correct 9 ms 12240 KB Output is correct
5 Correct 7 ms 12364 KB Output is correct
6 Correct 7 ms 12336 KB Output is correct
7 Correct 10 ms 12340 KB Output is correct
8 Correct 8 ms 12348 KB Output is correct
9 Correct 8 ms 12364 KB Output is correct
10 Correct 9 ms 12340 KB Output is correct
11 Correct 8 ms 12340 KB Output is correct
12 Correct 8 ms 12364 KB Output is correct
13 Correct 7 ms 12340 KB Output is correct
14 Correct 8 ms 12364 KB Output is correct
15 Correct 8 ms 12236 KB Output is correct
16 Correct 8 ms 12388 KB Output is correct
17 Correct 8 ms 12232 KB Output is correct
18 Correct 8 ms 12256 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 8 ms 12364 KB Output is correct
21 Correct 92 ms 20420 KB Output is correct
22 Correct 92 ms 20676 KB Output is correct
23 Correct 92 ms 20416 KB Output is correct
24 Correct 89 ms 20460 KB Output is correct
25 Correct 114 ms 20776 KB Output is correct
26 Correct 94 ms 20656 KB Output is correct
27 Correct 53 ms 18752 KB Output is correct
28 Correct 52 ms 19100 KB Output is correct
29 Correct 88 ms 20452 KB Output is correct
30 Correct 91 ms 20684 KB Output is correct
31 Correct 90 ms 20552 KB Output is correct
32 Correct 90 ms 20636 KB Output is correct
33 Correct 83 ms 19756 KB Output is correct
34 Correct 91 ms 20436 KB Output is correct
35 Correct 95 ms 20788 KB Output is correct
36 Correct 92 ms 20804 KB Output is correct
37 Correct 102 ms 19884 KB Output is correct
38 Correct 76 ms 19524 KB Output is correct
39 Correct 43 ms 18520 KB Output is correct
40 Correct 51 ms 18724 KB Output is correct
41 Correct 89 ms 20236 KB Output is correct
42 Correct 98 ms 20524 KB Output is correct
43 Correct 95 ms 20516 KB Output is correct
44 Correct 92 ms 20352 KB Output is correct
45 Correct 93 ms 20544 KB Output is correct
46 Correct 106 ms 20564 KB Output is correct
47 Correct 61 ms 19368 KB Output is correct
48 Correct 85 ms 20468 KB Output is correct
49 Correct 64 ms 18984 KB Output is correct
50 Correct 80 ms 19748 KB Output is correct
51 Correct 99 ms 20524 KB Output is correct
52 Correct 92 ms 20508 KB Output is correct
53 Correct 71 ms 19592 KB Output is correct
54 Correct 103 ms 20716 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12236 KB Output is correct
2 Correct 9 ms 12364 KB Output is correct
3 Correct 8 ms 12228 KB Output is correct
4 Correct 9 ms 12240 KB Output is correct
5 Correct 7 ms 12364 KB Output is correct
6 Correct 7 ms 12336 KB Output is correct
7 Correct 10 ms 12340 KB Output is correct
8 Correct 8 ms 12348 KB Output is correct
9 Correct 8 ms 12364 KB Output is correct
10 Correct 9 ms 12340 KB Output is correct
11 Correct 8 ms 12340 KB Output is correct
12 Correct 8 ms 12364 KB Output is correct
13 Correct 7 ms 12340 KB Output is correct
14 Correct 8 ms 12364 KB Output is correct
15 Correct 8 ms 12236 KB Output is correct
16 Correct 8 ms 12388 KB Output is correct
17 Correct 8 ms 12232 KB Output is correct
18 Correct 8 ms 12256 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 8 ms 12364 KB Output is correct
21 Incorrect 7 ms 12328 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12236 KB Output is correct
2 Correct 9 ms 12364 KB Output is correct
3 Correct 8 ms 12228 KB Output is correct
4 Correct 9 ms 12240 KB Output is correct
5 Correct 7 ms 12364 KB Output is correct
6 Correct 7 ms 12336 KB Output is correct
7 Correct 10 ms 12340 KB Output is correct
8 Correct 8 ms 12348 KB Output is correct
9 Correct 8 ms 12364 KB Output is correct
10 Correct 9 ms 12340 KB Output is correct
11 Correct 8 ms 12340 KB Output is correct
12 Correct 8 ms 12364 KB Output is correct
13 Correct 7 ms 12340 KB Output is correct
14 Correct 8 ms 12364 KB Output is correct
15 Correct 8 ms 12236 KB Output is correct
16 Correct 8 ms 12388 KB Output is correct
17 Correct 8 ms 12232 KB Output is correct
18 Correct 8 ms 12256 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 8 ms 12364 KB Output is correct
21 Incorrect 7 ms 12328 KB Output isn't correct
22 Halted 0 ms 0 KB -