Submission #108689

#	Time	Username	Problem	Language	Result	Execution time	Memory
108689		shoemakerjo	Examination (JOI19_examination)	C++14	100 / 100	1149 ms	48732 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
int n, q;
const int bil = 1000000000;
#define pii pair<int, int>
#define pp pair<int, pii>
#define mp make_pair


vector<pp> vals;
set<int>  as, bs;
map<int, int> am, bm;

struct BIT {

  vector<int> mvals; //going to want to merge two lists
  vector<int> csum; //the sum values

  int query(int num) {
    //return csum >= num
    //find the index of it in mvals
    int indo = lower_bound(mvals.begin(), mvals.end(), num) - mvals.begin();
    //maybe we should increase by 1
    // indo++;
    indo = mvals.size()-indo;

    if (num == 100) {
      // cout << " thing: " << indo << endl;
    }

    int res = 0;
    while (indo > 0) {
      res += csum[indo];
      indo -= indo & (-indo);
    }
    return res;
  }

  void update(int num) {
    int indo = lower_bound(mvals.begin(), mvals.end(), num) - mvals.begin();

    // indo++;
    // cout << " --mm--- " << mvals.size() << " :: " << indo << endl;
    indo = mvals.size()-indo;

    // cout << " ---- " << indo << endl;
    if (indo == 0) {
      cout << "weird weird" << endl;
      return;
    }
    while (indo < csum.size()) {
      csum[indo]++;
      indo += (indo) & (-indo);
    }
  }

};

set<int> bstuff[maxn]; //push back the b values each guy stores
BIT bigtree[maxn];

void update(int av, int bv) {

  // cout << "updating " << av << endl;

  av = n-av+1;

  while (av <= n) {

    // cout << "    " << av << endl;
    bigtree[av].update(bv);
    av += av & (-av);
  }
}


int query(int av, int bv) {

  // cout << "doing " << av << endl;

  av = n-av+1;
  int res = 0;
  while (av) {
    // cout << "    " << av << endl;
    res += bigtree[av].query(bv);
    av -= av & (-av);
  }
  return res;
}

void addval(int av, int bv) {

  av = n-av+1;
  // cout << "adding pair " << av << ", " << bv << endl;

  while (av <= n) {
    if (bigtree[av].mvals.size() == 0 ||
      bigtree[av].mvals.back() != bv) {
        bigtree[av].mvals.push_back(bv);
        bigtree[av].csum.push_back(0);
      }

    av += av & (-av);
  }
  // cout << " done adding" << endl;
}

vector<pp> msubs[maxn];
vector<pp> madds[maxn];

int ans[maxn];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> q;

  for (int i = 0; i <= n; i++) {
    bigtree[i].csum.push_back(0);
  }

  int av, bv;
  for (int i = 0; i < n; i++) {
    cin >> av >> bv;
    vals.push_back(mp(av+bv, mp(av, bv)));
    as.insert(av);

  }

  int curct = 0;

  vector<pii> nstuff;

  vector<int> acur;
  acur.push_back(-1);


  for (int vv : as) {
    am[vv] = ++curct;
    acur.push_back(vv);
  }

  sort(vals.begin(), vals.end());

  for (int i = 1; i <= n; i++) {
    av = vals[i-1].second.first;
    bv = vals[i-1].second.second;
    vals[i-1] = mp(vals[i-1].first, mp(am[av], bv));
    nstuff.push_back(pii(bv, am[av]));
  }

  sort(nstuff.begin(), nstuff.end());

  for (pii vp : nstuff) {
    av = vp.second;
    bv = vp.first;
    addval(av, bv);
  }

  // for (int i = 1; i <= n; i++) {
  //   cout << i << " : ";
  //   for (int vvv : bigtree[i].mvals) cout << vvv << " ";
  //   cout << endl;
  // }

  int xi, yi, zi;
  for (int i = 1; i <= q; i++) {
    cin >> xi >> yi >> zi;
    pp tempo = mp(zi, mp(-1, -1));
    //want first with this sum
    int indo = lower_bound(vals.begin(), vals.end(), tempo) - vals.begin();

    // cout << "    " << i << "'s indo : " << indo << endl;

    //everything with value >= indo should get me (insert at indo)
    if (indo-1 >= 0) msubs[indo-1].push_back(pp(i, pii(xi, yi)));
    madds[n].push_back(pp(i, pii(xi, yi)));
  }

  //we have the big tree

  for (int i = 0; i <= vals.size(); i++) {
    //insert my value
    if (i != vals.size()) {
      av = vals[i].second.first;
      bv = vals[i].second.second;

      // cout << "UPDATE: " << av << " - " << bv << endl;
      update(av, bv);
    }

    for (pp vp : msubs[i]) {
      int indo = vp.first;
      xi = vp.second.first;
      xi = lower_bound(acur.begin(), acur.end(), xi) - acur.begin();
      yi = vp.second.second;


      // cout << "      on " << i << " : " << indo << " " << query(xi, yi) << endl;

      ans[indo] -= query(xi, yi);
    }
    for (pp vp : madds[i]) {
      int indo = vp.first;
      xi = vp.second.first;
      xi = lower_bound(acur.begin(), acur.end(), xi) - acur.begin();

      yi = vp.second.second;

      ans[indo] += query(xi, yi);

      // cout << xi << " - " << yi << "  ::  " << query(xi, yi) << endl;
    }


  }

  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }

  cout.flush();
}

Compilation message (stderr)

examination.cpp: In member function 'void BIT::update(int)':
examination.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (indo < csum.size()) {
            ~~~~~^~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:186:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i <= vals.size(); i++) {
                   ~~^~~~~~~~~~~~~~
examination.cpp:188:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i != vals.size()) {
         ~~^~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57