oj.uz

Submission #521658

# Submission time Handle Problem Language Result Execution time Memory
521658 2022-02-02T17:20:23 Z cig32 Examination (JOI19_examination) C++17
100 / 100
 2527 ms 286140 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 = 6e5 + 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;
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(600000, 600000) - query(600000, e[i].b) 
        - query(e[i].a, 600000) + 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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 56652 KB Output is correct
2 Correct 41 ms 56644 KB Output is correct
3 Correct 41 ms 56676 KB Output is correct
4 Correct 45 ms 56716 KB Output is correct
5 Correct 42 ms 56648 KB Output is correct
6 Correct 41 ms 56560 KB Output is correct
7 Correct 66 ms 62888 KB Output is correct
8 Correct 66 ms 63044 KB Output is correct
9 Correct 69 ms 63120 KB Output is correct
10 Correct 62 ms 62532 KB Output is correct
11 Correct 68 ms 63396 KB Output is correct
12 Correct 65 ms 60156 KB Output is correct
13 Correct 65 ms 62784 KB Output is correct
14 Correct 65 ms 62660 KB Output is correct
15 Correct 64 ms 62788 KB Output is correct
16 Correct 68 ms 62952 KB Output is correct
17 Correct 70 ms 62368 KB Output is correct
18 Correct 60 ms 60228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1913 ms 218856 KB Output is correct
2 Correct 1991 ms 218868 KB Output is correct
3 Correct 1946 ms 218988 KB Output is correct
4 Correct 1472 ms 212948 KB Output is correct
5 Correct 1297 ms 252212 KB Output is correct
6 Correct 1084 ms 175044 KB Output is correct
7 Correct 1421 ms 218876 KB Output is correct
8 Correct 1767 ms 218820 KB Output is correct
9 Correct 1376 ms 219144 KB Output is correct
10 Correct 1138 ms 233252 KB Output is correct
11 Correct 1101 ms 189364 KB Output is correct
12 Correct 876 ms 179908 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1913 ms 218856 KB Output is correct
2 Correct 1991 ms 218868 KB Output is correct
3 Correct 1946 ms 218988 KB Output is correct
4 Correct 1472 ms 212948 KB Output is correct
5 Correct 1297 ms 252212 KB Output is correct
6 Correct 1084 ms 175044 KB Output is correct
7 Correct 1421 ms 218876 KB Output is correct
8 Correct 1767 ms 218820 KB Output is correct
9 Correct 1376 ms 219144 KB Output is correct
10 Correct 1138 ms 233252 KB Output is correct
11 Correct 1101 ms 189364 KB Output is correct
12 Correct 876 ms 179908 KB Output is correct
13 Correct 1864 ms 220768 KB Output is correct
14 Correct 2045 ms 218904 KB Output is correct
15 Correct 1961 ms 218936 KB Output is correct
16 Correct 1165 ms 212872 KB Output is correct
17 Correct 1234 ms 252416 KB Output is correct
18 Correct 1049 ms 175148 KB Output is correct
19 Correct 1890 ms 220904 KB Output is correct
20 Correct 1910 ms 220000 KB Output is correct
21 Correct 1478 ms 220672 KB Output is correct
22 Correct 1138 ms 233332 KB Output is correct
23 Correct 1074 ms 189368 KB Output is correct
24 Correct 894 ms 179772 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 56652 KB Output is correct
2 Correct 41 ms 56644 KB Output is correct
3 Correct 41 ms 56676 KB Output is correct
4 Correct 45 ms 56716 KB Output is correct
5 Correct 42 ms 56648 KB Output is correct
6 Correct 41 ms 56560 KB Output is correct
7 Correct 66 ms 62888 KB Output is correct
8 Correct 66 ms 63044 KB Output is correct
9 Correct 69 ms 63120 KB Output is correct
10 Correct 62 ms 62532 KB Output is correct
11 Correct 68 ms 63396 KB Output is correct
12 Correct 65 ms 60156 KB Output is correct
13 Correct 65 ms 62784 KB Output is correct
14 Correct 65 ms 62660 KB Output is correct
15 Correct 64 ms 62788 KB Output is correct
16 Correct 68 ms 62952 KB Output is correct
17 Correct 70 ms 62368 KB Output is correct
18 Correct 60 ms 60228 KB Output is correct
19 Correct 1913 ms 218856 KB Output is correct
20 Correct 1991 ms 218868 KB Output is correct
21 Correct 1946 ms 218988 KB Output is correct
22 Correct 1472 ms 212948 KB Output is correct
23 Correct 1297 ms 252212 KB Output is correct
24 Correct 1084 ms 175044 KB Output is correct
25 Correct 1421 ms 218876 KB Output is correct
26 Correct 1767 ms 218820 KB Output is correct
27 Correct 1376 ms 219144 KB Output is correct
28 Correct 1138 ms 233252 KB Output is correct
29 Correct 1101 ms 189364 KB Output is correct
30 Correct 876 ms 179908 KB Output is correct
31 Correct 1864 ms 220768 KB Output is correct
32 Correct 2045 ms 218904 KB Output is correct
33 Correct 1961 ms 218936 KB Output is correct
34 Correct 1165 ms 212872 KB Output is correct
35 Correct 1234 ms 252416 KB Output is correct
36 Correct 1049 ms 175148 KB Output is correct
37 Correct 1890 ms 220904 KB Output is correct
38 Correct 1910 ms 220000 KB Output is correct
39 Correct 1478 ms 220672 KB Output is correct
40 Correct 1138 ms 233332 KB Output is correct
41 Correct 1074 ms 189368 KB Output is correct
42 Correct 894 ms 179772 KB Output is correct
43 Correct 2179 ms 252032 KB Output is correct
44 Correct 2294 ms 257012 KB Output is correct
45 Correct 2527 ms 256040 KB Output is correct
46 Correct 1419 ms 240232 KB Output is correct
47 Correct 1525 ms 286140 KB Output is correct
48 Correct 950 ms 175940 KB Output is correct
49 Correct 2062 ms 254468 KB Output is correct
50 Correct 1974 ms 255400 KB Output is correct
51 Correct 1795 ms 253188 KB Output is correct
52 Correct 1550 ms 281048 KB Output is correct
53 Correct 1241 ms 224716 KB Output is correct