oj.uz

Submission #839412

# Submission time Handle Problem Language Result Execution time Memory
839412 2023-08-30T02:12:07 Z huutuan Examination (JOI19_examination) C++14
2 / 100
 3000 ms 324552 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

struct nigga{
   int x, y, z, i;
   nigga(int a=0, int b=0, int c=0, int d=0): x(a), y(b), z(c), i(d){}
   bool operator<(const nigga &a) const {
      return make_pair(-z, i)<make_pair(-a.z, a.i);
   }
};


struct FenwickTree{
   int n;
   unordered_map<int, unordered_map<int, int>> t;

   void init(int _n){
      n=_n;
   }

   void update(int x, int y, int val){
      for (int i=x; i<=n; i+=i&(-i))
         for (int j=y; j<=n; j+=j&(-j)) t[i][j]+=val;
   }

   int get(int x, int y){
      int ans=0;
      for (int i=x; i; i-=i&(-i))
         for (int j=y; j; j-=j&(-j)) ans+=t[i][j];
      return ans;
   }
} bit;

const int N=2e5+1;
int n, q, ans[N];
nigga a[N];

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   cin >> n >> q;
   vector<int> r, c;
   for (int i=1; i<=n; ++i) cin >> a[i].x >> a[i].y, a[i].z=a[i].x+a[i].y, r.push_back(a[i].x), c.push_back(a[i].y), a[i].i=i;
   for (int i=n+1; i<=n+q; ++i) cin >> a[i].x >> a[i].y >> a[i].z, r.push_back(a[i].x), c.push_back(a[i].y), a[i].i=i;
   sort(all(r)); sort(all(c)); r.resize(unique(all(r))-r.begin()); c.resize(unique(all(c))-c.begin());
   for (int i=1; i<=n+q; ++i) a[i].x=lower_bound(all(r), a[i].x)-r.begin()+1, a[i].y=lower_bound(all(c), a[i].y)-c.begin()+1;
   sort(a+1, a+n+q+1);
   bit.init(N-1);
   int cnt=0;
   for (int i=1; i<=n+q; ++i){
      if (a[i].i<=n) bit.update(a[i].x, a[i].y, 1), ++cnt;
      else ans[a[i].i-n]=cnt-(bit.get(a[i].x-1, bit.n)+bit.get(bit.n, a[i].y-1)-bit.get(a[i].x-1, a[i].y-1));
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 4 ms 6656 KB Output is correct
7 Correct 48 ms 17100 KB Output is correct
8 Correct 48 ms 17088 KB Output is correct
9 Correct 50 ms 17100 KB Output is correct
10 Correct 27 ms 11476 KB Output is correct
11 Correct 31 ms 11056 KB Output is correct
12 Correct 16 ms 6740 KB Output is correct
13 Correct 45 ms 17292 KB Output is correct
14 Correct 47 ms 17436 KB Output is correct
15 Correct 49 ms 17220 KB Output is correct
16 Correct 28 ms 10736 KB Output is correct
17 Correct 23 ms 11340 KB Output is correct
18 Correct 16 ms 6740 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 324552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 324552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 4 ms 6656 KB Output is correct
7 Correct 48 ms 17100 KB Output is correct
8 Correct 48 ms 17088 KB Output is correct
9 Correct 50 ms 17100 KB Output is correct
10 Correct 27 ms 11476 KB Output is correct
11 Correct 31 ms 11056 KB Output is correct
12 Correct 16 ms 6740 KB Output is correct
13 Correct 45 ms 17292 KB Output is correct
14 Correct 47 ms 17436 KB Output is correct
15 Correct 49 ms 17220 KB Output is correct
16 Correct 28 ms 10736 KB Output is correct
17 Correct 23 ms 11340 KB Output is correct
18 Correct 16 ms 6740 KB Output is correct
19 Execution timed out 3081 ms 324552 KB Time limit exceeded
20 Halted 0 ms 0 KB -