oj.uz

Submission #998386

# Submission time Handle Problem Language Result Execution time Memory
998386 2024-06-13T19:13:54 Z trucmai Examination (JOI19_examination) C++17
100 / 100
 878 ms 53712 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define ll long long
#define endl '\n'
const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
const ll INF = 1e18;
void solver();
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1; // cin>>t;
  while (t--)
    solver();
}
int n,q; 
ll res[N],max_val = 1;
struct op{
    ll x = 0,y = 0,z = 0; int idx = 0,val = 0;
    op(ll x,ll y,ll z,int i,int v):x(x),y(y),z(z),idx(i),val(v){}
    bool operator < (const op &b) const{
        op a = *this;
        if(a.x == b.x) return a.val > b.val;
	    return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x);
    }
};

vector<op>v;
void compress(){
    map<ll,int>mp;
    for(int i = 0;i < n + q;++i){
        mp[v[i].x] = true;
        mp[v[i].y] = true;
        mp[v[i].z] = true;
    }
	for(auto i : mp) mp[i.first] = max_val++;
	for(int i = 0; i < n + q; i++){
		v[i].x = mp[v[i].x];
		v[i].y = mp[v[i].y];
		v[i].z = mp[v[i].z];
	}
}

struct fenwick{
    vector<ll>tr; int n;
    fenwick(){}
    void build(int sz){
        n = sz;
        tr.resize(n + 2);
    }
    int lowbit(int i){return i&(-i);}
    void update(int i,ll val){
        for(;i <= max_val;i += lowbit(i)) tr[i] += val;
    }
    ll sum(int i){
        ll res = 0;
        for(;i > 0;i -= lowbit(i)) res += tr[i];
        return res;
    }
    ll get(int l,int r){
        return sum(r) - sum(l - 1);
    } 
}bit;

void calc_cont(int l,int m,int r){
    int a = l,b = m + 1;
    vector<op>tmp; vector<pair<int,int>>record;
    while(a <= m && b <= r){
        if(v[a].y >= v[b].y){
            bit.update(v[a].z,v[a].val);            
            record.emplace_back(v[a].z,v[a].val);
            tmp.push_back(v[a]);
            ++a;
        }else{
            res[v[b].idx] += bit.get(v[b].z,max_val);
            tmp.push_back(v[b]);
            ++b;
        }
    }
    while(a <= m){
        tmp.push_back(v[a]);
        ++a;
    }
    while(b <= r){
        res[v[b].idx] += bit.get(v[b].z,max_val);
        tmp.push_back(v[b]);
        ++b;
    }
    for(int i = l;i <= r;++i) v[i] = tmp[i - l];
    for(auto &[pos,val] : record) bit.update(pos,-val);
}

void cdq(int l,int r){
    if(l == r) return;
    int m = (r+l) >> 1; 
    cdq(l,m); cdq(m+1,r);
    calc_cont(l,m,r);
}

void solver() {
    cin>>n>>q;
    for(int i = 0;i < n;++i){
        ll x,y; cin>>x>>y;
        v.push_back({x,y,x + y,i,1});
    }    
    for(int i = n;i < n + q;++i){
        ll x,y,z; cin>>x>>y>>z;
        v.push_back({x,y,z,i,0});
    }
    compress();
    sort(v.begin(),v.end());
    bit.build(max_val);
    cdq(0,n + q - 1);
    for(int i = n;i < n + q;++i) cout<<res[i]<<endl; 
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 12 ms 1756 KB Output is correct
8 Correct 12 ms 1936 KB Output is correct
9 Correct 14 ms 1760 KB Output is correct
10 Correct 9 ms 1504 KB Output is correct
11 Correct 9 ms 1504 KB Output is correct
12 Correct 4 ms 1056 KB Output is correct
13 Correct 11 ms 1728 KB Output is correct
14 Correct 10 ms 1756 KB Output is correct
15 Correct 10 ms 1760 KB Output is correct
16 Correct 7 ms 1408 KB Output is correct
17 Correct 9 ms 1376 KB Output is correct
18 Correct 3 ms 944 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 31580 KB Output is correct
2 Correct 443 ms 28344 KB Output is correct
3 Correct 433 ms 30388 KB Output is correct
4 Correct 313 ms 28628 KB Output is correct
5 Correct 299 ms 29028 KB Output is correct
6 Correct 116 ms 27316 KB Output is correct
7 Correct 427 ms 29880 KB Output is correct
8 Correct 433 ms 30424 KB Output is correct
9 Correct 391 ms 29620 KB Output is correct
10 Correct 273 ms 31024 KB Output is correct
11 Correct 289 ms 29932 KB Output is correct
12 Correct 95 ms 26620 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 31580 KB Output is correct
2 Correct 443 ms 28344 KB Output is correct
3 Correct 433 ms 30388 KB Output is correct
4 Correct 313 ms 28628 KB Output is correct
5 Correct 299 ms 29028 KB Output is correct
6 Correct 116 ms 27316 KB Output is correct
7 Correct 427 ms 29880 KB Output is correct
8 Correct 433 ms 30424 KB Output is correct
9 Correct 391 ms 29620 KB Output is correct
10 Correct 273 ms 31024 KB Output is correct
11 Correct 289 ms 29932 KB Output is correct
12 Correct 95 ms 26620 KB Output is correct
13 Correct 499 ms 33976 KB Output is correct
14 Correct 459 ms 32400 KB Output is correct
15 Correct 439 ms 29468 KB Output is correct
16 Correct 359 ms 26804 KB Output is correct
17 Correct 359 ms 30644 KB Output is correct
18 Correct 129 ms 27680 KB Output is correct
19 Correct 473 ms 36024 KB Output is correct
20 Correct 474 ms 29980 KB Output is correct
21 Correct 501 ms 32708 KB Output is correct
22 Correct 279 ms 29596 KB Output is correct
23 Correct 287 ms 30368 KB Output is correct
24 Correct 89 ms 24388 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 12 ms 1756 KB Output is correct
8 Correct 12 ms 1936 KB Output is correct
9 Correct 14 ms 1760 KB Output is correct
10 Correct 9 ms 1504 KB Output is correct
11 Correct 9 ms 1504 KB Output is correct
12 Correct 4 ms 1056 KB Output is correct
13 Correct 11 ms 1728 KB Output is correct
14 Correct 10 ms 1756 KB Output is correct
15 Correct 10 ms 1760 KB Output is correct
16 Correct 7 ms 1408 KB Output is correct
17 Correct 9 ms 1376 KB Output is correct
18 Correct 3 ms 944 KB Output is correct
19 Correct 450 ms 31580 KB Output is correct
20 Correct 443 ms 28344 KB Output is correct
21 Correct 433 ms 30388 KB Output is correct
22 Correct 313 ms 28628 KB Output is correct
23 Correct 299 ms 29028 KB Output is correct
24 Correct 116 ms 27316 KB Output is correct
25 Correct 427 ms 29880 KB Output is correct
26 Correct 433 ms 30424 KB Output is correct
27 Correct 391 ms 29620 KB Output is correct
28 Correct 273 ms 31024 KB Output is correct
29 Correct 289 ms 29932 KB Output is correct
30 Correct 95 ms 26620 KB Output is correct
31 Correct 499 ms 33976 KB Output is correct
32 Correct 459 ms 32400 KB Output is correct
33 Correct 439 ms 29468 KB Output is correct
34 Correct 359 ms 26804 KB Output is correct
35 Correct 359 ms 30644 KB Output is correct
36 Correct 129 ms 27680 KB Output is correct
37 Correct 473 ms 36024 KB Output is correct
38 Correct 474 ms 29980 KB Output is correct
39 Correct 501 ms 32708 KB Output is correct
40 Correct 279 ms 29596 KB Output is correct
41 Correct 287 ms 30368 KB Output is correct
42 Correct 89 ms 24388 KB Output is correct
43 Correct 852 ms 53712 KB Output is correct
44 Correct 873 ms 53432 KB Output is correct
45 Correct 878 ms 51640 KB Output is correct
46 Correct 509 ms 37048 KB Output is correct
47 Correct 531 ms 42860 KB Output is correct
48 Correct 138 ms 26300 KB Output is correct
49 Correct 857 ms 51420 KB Output is correct
50 Correct 876 ms 51984 KB Output is correct
51 Correct 837 ms 51908 KB Output is correct
52 Correct 434 ms 37032 KB Output is correct
53 Correct 354 ms 33980 KB Output is correct