Submission #1273408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273408		nthvn	Examination (JOI19_examination)	C++20	0 / 100	200 ms	8804 KiB

examination

#include "bits/stdc++.h"
using namespace std;
#define cerr if(0) cerr
#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N = 2e5+5;
int n,q,tot, fans[N];
struct DATA{
	int x,y,z,id;
	bool operator < (const DATA &o ) const{
		return x> o.x;
	}
	void print(){
		cerr<<x<<" "<<y<<" "<<z<<"\n";
	}
} a[N], t[N];
struct BITREV{
	int bit[N];
	void update(int i, int x){
		for(;i;i-=i&-i) bit[i]+=x;
	}
	int get(int i){
		int ans =0;
		for(;i<=tot;i+=i&-i) ans+= bit[i];
		return ans;
	}
}bit;

void compress(){
	vector<int> X,Y,Z;
	for(int i=1;i<=tot;i++) {
		X.pb(a[i].x), Y.pb(a[i].y), Z.pb(a[i].z);
	}
	sort(all(X));
	sort(all(Y));
	sort(all(Z));
	for(int i=1;i<=tot;i++){
		a[i].x = lower_bound(all(X), a[i].x) - X.begin()+1;
		a[i].y = lower_bound(all(Y), a[i].y) - Y.begin()+1;
		a[i].z = lower_bound(all(Z), a[i].z) - Z.begin()+1;
	}
}

vector<pii> hist;
void mg(int x, int y, int u, int v){
	
	int st= x-1;
	int L= x, R=u;
	
	while(L<=y&&R<=v){
		if(a[L].y>= a[R].y){
			t[++st] = a[L];
			int z= a[L].z;
			if(!a[L].id){
				hist.pb({z,-1});
				bit.update(z,1);
			}
			L++;
		}
		else{
			t[++st] = a[R];
			int z= a[R].z;
			if(a[R].id) fans[a[R].id] += bit.get(z);
			R++;
		}
	}
	while(L<=y){
		t[++st]= a[L++];
	}
	while(R<=v){
		if(a[R].id) fans[a[R].id] += bit.get(a[R].z);
		t[++st]= a[R++];
	}
	cerr<<x<<" "<<y<<" "<<u<<" "<<v<<" "<<L<<" "<<R<<"\n";
	for(int i=x;i<=v;i++) a[i].print();
	cerr<<"__________________\n";
	for(int i=x;i<=v;i++) t[i].print();
	cerr<<"\n\n";
	
	for(int i=x;i<=v;i++) a[i] = t[i];
	while(sz(hist)){
		bit.update(hist.back().fi, hist.back().se);
		hist.pop_back();
	}
}

void dnc(int l, int r){
	if(l==r) return;
	int mid =(l+r)>>1;
	dnc(l,mid);
	dnc(mid+1,r);
	mg(l,mid, mid+1,r);
}

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("TASK.INP", "r")){
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		int x,y; cin>>x>>y;
		a[++tot] = {x,y,x+y,0};
	}
	for(int i=1;i<=q;i++){
		int x,y,z; cin>>x>>y>>z;
		a[++tot] = {x,y,z,i};
	}
	compress();
	cerr<<"A\n";
	for(int i=1;i<=n;i++) a[i].print();
	cerr<<"\nB\n";
	for(int i=n+1;i<=tot;i++) a[i].print();
	sort(a+1,a+tot+1);
	
	cerr<<"\nT\n";
	for(int i=1;i<=tot;i++) a[i].print();
	cerr<<"\n\n";
	
	dnc(1,tot);
	
	for(int i=1;i<=q;i++) cout<<fans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:104:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:105:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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