oj.uz

Submission #521653

# Submission time Handle Problem Language Result Execution time Memory
521653 2022-02-02T16:56:49 Z cig32 Examination (JOI19_examination) C++17
41 / 100
 1674 ms 202120 KB 
#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 = 2e5 + 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 binary matrices
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];
  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;
  }
  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;
  }
  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(200001, 200001) - query(200001, e[i].b) 
        - query(e[i].a, 200001) + 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19096 KB Output is correct
2 Correct 14 ms 19084 KB Output is correct
3 Correct 15 ms 19080 KB Output is correct
4 Runtime error 27 ms 38464 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1607 ms 164524 KB Output is correct
2 Correct 1630 ms 164428 KB Output is correct
3 Correct 1618 ms 164468 KB Output is correct
4 Correct 1310 ms 160556 KB Output is correct
5 Correct 1038 ms 201784 KB Output is correct
6 Correct 921 ms 131684 KB Output is correct
7 Correct 1140 ms 164420 KB Output is correct
8 Correct 1513 ms 164276 KB Output is correct
9 Correct 1065 ms 164260 KB Output is correct
10 Correct 965 ms 187488 KB Output is correct
11 Correct 878 ms 136504 KB Output is correct
12 Correct 834 ms 140884 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1607 ms 164524 KB Output is correct
2 Correct 1630 ms 164428 KB Output is correct
3 Correct 1618 ms 164468 KB Output is correct
4 Correct 1310 ms 160556 KB Output is correct
5 Correct 1038 ms 201784 KB Output is correct
6 Correct 921 ms 131684 KB Output is correct
7 Correct 1140 ms 164420 KB Output is correct
8 Correct 1513 ms 164276 KB Output is correct
9 Correct 1065 ms 164260 KB Output is correct
10 Correct 965 ms 187488 KB Output is correct
11 Correct 878 ms 136504 KB Output is correct
12 Correct 834 ms 140884 KB Output is correct
13 Correct 1434 ms 164776 KB Output is correct
14 Correct 1674 ms 164712 KB Output is correct
15 Correct 1629 ms 164564 KB Output is correct
16 Correct 954 ms 160928 KB Output is correct
17 Correct 998 ms 202120 KB Output is correct
18 Correct 935 ms 131880 KB Output is correct
19 Correct 1416 ms 164804 KB Output is correct
20 Correct 1508 ms 164688 KB Output is correct
21 Correct 1184 ms 164888 KB Output is correct
22 Correct 964 ms 187588 KB Output is correct
23 Correct 954 ms 136312 KB Output is correct
24 Correct 835 ms 140992 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19096 KB Output is correct
2 Correct 14 ms 19084 KB Output is correct
3 Correct 15 ms 19080 KB Output is correct
4 Runtime error 27 ms 38464 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -