Submission #539406

#	Time	Username	Problem	Language	Result	Execution time	Memory
539406		cadmiumsky	Food Court (JOI21_foodcourt)	C++14	0 / 100	1086 ms	25844 KiB

foodcourt

#include <bits/stdc++.h>
#define int ll
#define ll long long
using namespace std;

const int nmax = 25e4 + 5;

#define lsb(x) (x & (-x))
struct AIB {
  int tree[nmax];
  int len;
  void init(int nlen) {
    len = nlen;
    memset(tree, 0, sizeof(tree));
  }
  int query(int poz) {
    int sum = 0;
    while(poz > 0)
      sum += tree[poz], poz -= lsb(poz);
    return sum;
  }
  void upd(int poz, int val) {
    while(poz <= len)
      tree[poz] += val, poz += lsb(poz);
  }
  void upd(int l, int r, int val) {
    upd(l, val);
    upd(r + 1, -val);
  }
};

int n, m, q;

namespace {
  namespace AINT { // mai mult ca sigur nu asa se scrie Beats ;-; 
    AIB total;
    vector<int> sus;
    struct Node {
      ll min1, min2, lazy;
      Node operator + (const Node& x) const {
        Node rez;
        rez.lazy = 0; //??
        sus.resize(4);
        sus[0] = min1;
        sus[1] = min2;
        sus[2] = x.min2;
        sus[3] = x.min1;
        sort(sus.begin(), sus.end());
        sus.resize(distance(sus.begin(), unique(sus.begin(), sus.end())));
        rez.min1 = sus[0];
        rez.min2 = sus[1];
        return rez;
      }
    } aint[nmax * 4];
    void pushmin(int node, ll val) { 
      aint[node].min1 = max(aint[node].min1, val);
    }
    void pushsum(int node, int cl, int cr) {
      aint[node].min1 += aint[node].lazy;
      aint[node].min2 += aint[node].lazy;
      if(cl != cr) {
        aint[2 * node].lazy += aint[node].lazy;
        aint[2 * node + 1].lazy += aint[node].lazy;
      }
      aint[node].lazy = 0;
    }
    void prop(int node, int cl, int cr, ll val) {
      pushsum(node, cl, cr);
      pushmin(node, val);
      if(cl == cr)
        return;
      int mid = cl + cr >> 1;
      pushsum(2 * node, cl, mid);
      pushmin(2 * node, val);
      pushsum(2 * node + 1, mid + 1, cr);
      pushmin(2 * node + 1, val);
    }
    void addv(int l, int r, ll val, int node = 1, int cl = 1, int cr = n) {
      prop(node, cl, cr, -1e15 - 5);
      if(l <= cl && cr <= r) {
        aint[node].lazy += val;
        prop(node, cl, cr, -1e15 - 5);
        return;
      }
      if(r < cl || cr < l)
        return;
      int mid = cl + cr >> 1;
      addv(l, r, val, 2 * node, cl, mid);
      addv(l, r, val, 2 * node + 1, mid + 1, cr);
      aint[node] = aint[2 * node] + aint[2 * node + 1];
    }
    void chmin(int l, int r, int node = 1, int cl = 1, int cr = n) {
      prop(node, cl, cr, -1e15 - 5);
      if(r < cl || cr < l || aint[node].min1 >= 0)
        return;
      if(l <= cl && cr <= r && aint[node].min2 >= 0) {
        //cerr << "+ " << l << ' ' << cl << ' ' << cr << ' ' << r << ' '<< aint[node].min1 << ' ' << aint[node].min2 << '\n';
        prop(node, cl, cr, 0);
        //cerr << "+ " << cl << ' ' << cr << ' '<< aint[node].min1 << ' ' << aint[node].min2 << '\n';
        
        return;
      }
      int mid = cl + cr >> 1;
      chmin(l, r, 2 * node, cl, mid);
      chmin(l, r, 2 * node + 1, mid + 1, cr);
      aint[node] = aint[2 * node] + aint[2 * node + 1];
      return;
    }
    int getval(int poz, int node = 1, int cl = 1, int cr = n) {
      prop(node, cl, cr, aint[node].min1);
      if(cl == cr)
        return aint[node].min1;
      int mid = cl + cr >> 1;
      if(poz <= mid)
        return getval(poz, 2 * node, cl, mid);
      return getval(poz, 2 * node + 1, mid + 1, cr);
    }
    void add(int l, int r, ll val) {
      addv(l, r, val);
      total.upd(l, r, max(0LL, val));
    }
    int query(int queue, int poz) {
      int all = total.query(queue);
      int current = getval(queue);
      //cout << all << ' ' << current << ' ' << poz << '\n';
      if(poz > current)
        return -1;
      return all - current + poz; 
    }
    void construct(int node = 1, int cl = 1, int cr = n) {
      aint[node].min2 = 1e15 + 15;
      if(cl == cr)
        return;
      int mid = cl + cr >> 1;
      construct(2 * node, cl, mid);
      construct(2 * node + 1, mid + 1, cr);
    }
  }
  namespace CONCRETE { // AINT persistent sau AINT cu Treap (sau cu sume partiale, ce destept eram in trecut lmfao) in nod sau Cautare Binara in Paralel 
    // aici voi incerca Cautare Binara in paralel
    struct Query {
      int temp, queue, poz, iter;
      bool operator < (const Query& x) const { return temp < x.temp; }
    };
    int sol[nmax];
    AIB contor;
    vector<Query> constqs, qs;
    vector< tuple<int,int, int, int> > update;
    void tour() {
      int i = 0, ptr = 0;
      contor.init(n + 2);
      sort(qs.begin(), qs.end());
      for(auto [l, r, dim, color] : update) {
        contor.upd(l, r, dim);
        i++;
        while(qs.size() > ptr && qs[ptr].temp < i) {
          if(contor.query(qs[ptr].queue) < qs[ptr].poz)
            sol[qs[ptr].iter] = qs[ptr].temp; 
          ptr++;
        }
      }
    }
    void print() {
      for(int i = 0; i < qs.size(); i++) {
        //cerr << qs[i].poz << ' ' << qs[i].temp << '\n';
        if(qs[i].poz == -1)
          cout << "0\n";
        else
          cout << get<3>(update[sol[i] + 1]) << '\n';
      }
    }
    void cbin() {
      for(int i = 0; i < constqs.size(); i++)
        sol[i] = -1;
      qs.resize(constqs.size());
      for(int i = 17; i >= 0; i--) {
        for(int j = 0; j < qs.size(); j++)
          qs[j] = constqs[j], qs[j].temp = sol[j] + (1 << i); 
        tour();
      }
      print(); 
    }
  }
  namespace READ {
    void read() {
      cin >> n >> m >> q;
      AINT::construct();
      AINT::total.init(n + 1);
      ll t, l, r, c, k;
      for(int i = 0; i < q; i++) {
        cin >> t;
        if(t == 1) {
          cin >> l >> r >> c >> k;
          CONCRETE::update.push_back({l, r, k, c});
          AINT::add(l, r, k);
        }
        else if(t == 2) {
          cin >> l >> r >> c;
          AINT::add(l, r, -c);
          AINT::chmin(l, r);
        }
        else {
          cin >> l >> r;
          k = AINT::query(l, r);
          //cout << k << '\n';
          CONCRETE::constqs.push_back(CONCRETE::Query{1097, l, k, CONCRETE::constqs.size()});
        }
      }
    }
  }
}



signed main() {
  ::READ::read();
  ::CONCRETE::cbin();
  return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void {anonymous}::AINT::prop(long long int, long long int, long long int, long long int)':
foodcourt.cpp:72:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::AINT::addv(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:87:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::AINT::chmin(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:103:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
foodcourt.cpp: In function 'long long int {anonymous}::AINT::getval(long long int, long long int, long long int, long long int)':
foodcourt.cpp:113:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::AINT::construct(long long int, long long int, long long int)':
foodcourt.cpp:134:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::CONCRETE::tour()':
foodcourt.cpp:153:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |       for(auto [l, r, dim, color] : update) {
      |                ^
foodcourt.cpp:156:25: warning: comparison of integer expressions of different signedness: 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  156 |         while(qs.size() > ptr && qs[ptr].temp < i) {
      |               ~~~~~~~~~~^~~~~
foodcourt.cpp: In function 'void {anonymous}::CONCRETE::print()':
foodcourt.cpp:164:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |       for(int i = 0; i < qs.size(); i++) {
      |                      ~~^~~~~~~~~~~
foodcourt.cpp: In function 'void {anonymous}::CONCRETE::cbin()':
foodcourt.cpp:173:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |       for(int i = 0; i < constqs.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~~
foodcourt.cpp:177:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |         for(int j = 0; j < qs.size(); j++)
      |                        ~~^~~~~~~~~~~
foodcourt.cpp: In function 'void {anonymous}::READ::read()':
foodcourt.cpp:206:89: warning: narrowing conversion of '{anonymous}::CONCRETE::constqs.std::vector<{anonymous}::CONCRETE::Query>::size()' from 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  206 |           CONCRETE::constqs.push_back(CONCRETE::Query{1097, l, k, CONCRETE::constqs.size()});
      |                                                                   ~~~~~~~~~~~~~~~~~~~~~~^~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11