Submission #521657

#	Time	Username	Problem	Language	Result	Execution time	Memory
521657		cig32	Examination (JOI19_examination)	C++17	43 / 100	1882 ms	223024 KiB

examination

#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
typedef tree<pair<pair<int, int>, int>, null_type, less<pair<pair<int, int>, int> >, rb_tree_tag, tree_order_statistics_node_update> OST;
#define int long long

int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
OST bit[MAXN]; // 2D bit in regular matrices but only supporting single add/del
int id = 0;
map<pair<int, int>, queue<int> > mp;
void insert(int x, int y) {
  id++;
  mp[{y, x}].push(id);
  for(;x<MAXN;x+=x&-x) bit[x].insert({{y, x}, id});
}
void erase(int x, int y) {
  int ono = mp[{y, x}].front(); mp[{y, x}].pop();
  for(;x<MAXN;x+=x&-x) bit[x].erase({{y, x}, ono});
}
int query(int x, int y) {
  int sum = 0;
  for(;x;x-=x&-x) sum += bit[x].order_of_key({{y+1, 0}, 0});
  return sum;
}
struct event {
  int type; // type = 0: "insert", type > 0: "query"
  int a, b, c;
};
bool cmp(event x, event y) {
  if(x.c == y.c) return x.type < y.type;
  return x.c > y.c;
}
void solve(int tc) {
  int n, q;
  cin >> n >> q;
  event e[n + q + 1];
  set<int> s;
  for(int i=1; i<=n; i++) {
    e[i].type = 0;
    cin >> e[i].a >> e[i].b;
    e[i].c = e[i].a + e[i].b;
    s.insert(e[i].a);
    s.insert(e[i].b);
    s.insert(e[i].c);
  }
  for(int i=1; i<=q; i++) {
    e[n+i].type = i;
    cin >> e[n+i].a >> e[n+i].b >> e[n+i].c;
    s.insert(e[n+i].a);
    s.insert(e[n+i].b);
    s.insert(e[n+i].c);
  }
  int nxt = 0;
  unordered_map<int, int> is;
  for(int x: s) {
    is[x] = ++nxt;
  }
  for(int i=1; i<=n+q; i++) {
    e[i].a = is[e[i].a];
    e[i].b = is[e[i].b];
    e[i].c = is[e[i].c];
  }
  sort(e + 1, e+n+q + 1, cmp);
  int ans[q+1];
  for(int i=1; i<=n+q; i++) {
    if(e[i].type == 0) {
      insert(e[i].a + 1, e[i].b + 1);
    }
    else {
      ans[e[i].type] = query(300000, 300000) - query(300000, e[i].b) 
        - query(e[i].a, 300000) + query(e[i].a, e[i].b);
    }
  }
  for(int i=1; i<=q; i++) {
    cout << ans[i] << "\n";
  }
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

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