oj.uz

Submission #803576

# Submission time Handle Problem Language Result Execution time Memory
803576 2023-08-03T04:57:39 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
10 / 25
 677 ms 17912 KB 
#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using ull=unsigned long long;
using db=long double;
using pii=array<int,2>;
using pll=array<ll,2>;
using pdb=array<db,2>;
using tii=array<int,3>;
using tll=array<ll,3>;
using tdb=array<db,3>;
using ti4=array<int,4>;
using tl4=array<ll,4>;
using td4=array<db,4>;
//using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<> gen(1,100);
template <int MOD_> struct modnum{
private:
	int v;
public:
	static const int MOD = MOD_;
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
	friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
	friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
	friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	friend modnum pow(modnum a, ll p) {
		modnum ans = 1;
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	modnum operator ~ () const {
		modnum res;
		res.v = pow((modnum)v, MOD - 2).v;
		return res;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}
	modnum operator-() const { return modnum(-v); }
	modnum& operator++() { return *this += 1; }
	modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
	modnum& operator--() { return *this -= 1; }
	modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
	friend ostream& operator<<(std::ostream& os, const modnum& o)
	{
		os << o.v;
		return os;
	}
	friend istream& operator>>(std::istream& is, modnum& o)
	{
		is >> o.v;
		return is;
	}
};
const ll mod=998244353,inf=1e18;
const int N=2e5+5,M=66,L=60;
using mi=modnum<mod>;
ll pw[M];
int n,q;
ll x[N],y[N];
int c[N],d[N],ans[N];
int odr[N],cur[N],nodr[N];
vector<tl4> V[M];
int p,sz;
void solve(int a,int l,int r){
	int k=r-l+1;
	for(int i=1;i<=k;i++) cur[i]=odr[i+l-1];
	for(int b=0;b<L&&p<sz;b++){
		if(V[a][p][0]!=x[cur[1]]%pw[a]) return;
		if(b){
			int m=0;
			for(int i=1;i<=k;i++){
				if(y[cur[i]]%pw[b]<pw[b-1]) nodr[++m]=cur[i];
			}
			for(int i=1;i<=k;i++){
				if(y[cur[i]]%pw[b]>=pw[b-1]) nodr[++m]=cur[i];
			}
			for(int i=1;i<=k;i++) cur[i]=nodr[i];
		}
		if(V[a][p][1]!=b) continue;
		for(int i=1;i<=k&&p<sz;i++){
			if(V[a][p][0]!=x[cur[1]]%pw[a]) return;
			if(V[a][p][1]!=b) break;
			ll v1=V[a][p][2],v2=y[cur[i]]%pw[b];
			if(v1<v2){
				p++;
				continue;
			}
			if(v1>v2) continue;
			int j=i;
			while(j+1<=k&&y[cur[j+1]]%pw[b]==v1) j++;
			ll s=V[a][p][3];
			p++;
			while(p<sz&&V[a][p][0]==x[cur[1]]%pw[a]&&V[a][p][1]==b&&V[a][p][2]==v1){
				s+=V[a][p][3];
				p++;
			}
			for(int ii=i;ii<=j;ii++) if(a<=c[cur[ii]]&&b<=d[cur[ii]]) ans[cur[ii]]+=s;
			i=j;
		}
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>q;
	pw[0]=1;
	for(int i=1;i<=60;i++) pw[i]=pw[i-1]*2;
	for(int i=1;i<=n;i++){
		ll x,y; int v;
		cin>>x>>y>>v;
		int a=0,b=0;
		while(pw[a+1]<=x) a++;
		while(pw[b+1]<=y) b++;
		V[a].push_back({x%pw[a],b,y%pw[b],v});
	}
	for(int i=1;i<=q;i++){
		cin>>x[i]>>y[i];
		while(pw[c[i]+1]<=x[i]) c[i]++;
		while(pw[d[i]+1]<=y[i]) d[i]++;
	}
	for(int i=1;i<=q;i++) odr[i]=i;
	for(int b=0;b<L;b++){
		if(b){
			int m=0;
			for(int i=1;i<=q;i++){
				if(x[odr[i]]%pw[b]<pw[b-1]) nodr[++m]=odr[i];
			}
			for(int i=1;i<=q;i++){
				if(x[odr[i]]%pw[b]>=pw[b-1]) nodr[++m]=odr[i];
			}
			for(int i=1;i<=q;i++) odr[i]=nodr[i];
		}
		sort(V[b].begin(),V[b].end());
		sz=V[b].size();
		p=0;
		for(int l=1;l<=q&&p<sz;l++){
			int r=l;
			while(r+1<=q&&x[odr[l]]%pw[b]==x[odr[r+1]]%pw[b]) r++;
			while(p<sz&&V[b][p][0]<x[odr[l]]%pw[b]) p++;
			if(p<sz&&x[odr[l]]%pw[b]==V[b][p][0]) solve(b,l,r);
			l=r;
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 468 KB Output is correct
3 Correct 8 ms 484 KB Output is correct
4 Correct 26 ms 468 KB Output is correct
5 Correct 25 ms 576 KB Output is correct
6 Correct 16 ms 584 KB Output is correct
7 Correct 16 ms 588 KB Output is correct
8 Correct 16 ms 468 KB Output is correct
9 Correct 16 ms 596 KB Output is correct
10 Correct 15 ms 584 KB Output is correct
11 Correct 16 ms 468 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 14792 KB Output is correct
2 Correct 451 ms 14760 KB Output is correct
3 Correct 677 ms 17804 KB Output is correct
4 Correct 672 ms 17708 KB Output is correct
5 Correct 460 ms 17532 KB Output is correct
6 Correct 472 ms 17804 KB Output is correct
7 Correct 458 ms 17616 KB Output is correct
8 Correct 454 ms 17656 KB Output is correct
9 Correct 461 ms 17912 KB Output is correct
10 Correct 457 ms 17580 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 208 ms 7604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 468 KB Output is correct
3 Correct 8 ms 484 KB Output is correct
4 Correct 26 ms 468 KB Output is correct
5 Correct 25 ms 576 KB Output is correct
6 Correct 16 ms 584 KB Output is correct
7 Correct 16 ms 588 KB Output is correct
8 Correct 16 ms 468 KB Output is correct
9 Correct 16 ms 596 KB Output is correct
10 Correct 15 ms 584 KB Output is correct
11 Correct 16 ms 468 KB Output is correct
12 Correct 439 ms 14792 KB Output is correct
13 Correct 451 ms 14760 KB Output is correct
14 Correct 677 ms 17804 KB Output is correct
15 Correct 672 ms 17708 KB Output is correct
16 Correct 460 ms 17532 KB Output is correct
17 Correct 472 ms 17804 KB Output is correct
18 Correct 458 ms 17616 KB Output is correct
19 Correct 454 ms 17656 KB Output is correct
20 Correct 461 ms 17912 KB Output is correct
21 Correct 457 ms 17580 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Incorrect 208 ms 7604 KB Output isn't correct
24 Halted 0 ms 0 KB -