oj.uz

Submission #803583

# Submission time Handle Problem Language Result Execution time Memory
803583 2023-08-03T04:59:27 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
10 / 25
 677 ms 17900 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++;
				i--;
				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 564 KB Output is correct
3 Correct 8 ms 556 KB Output is correct
4 Correct 26 ms 468 KB Output is correct
5 Correct 24 ms 580 KB Output is correct
6 Correct 17 ms 596 KB Output is correct
7 Correct 17 ms 596 KB Output is correct
8 Correct 16 ms 580 KB Output is correct
9 Correct 16 ms 580 KB Output is correct
10 Correct 16 ms 580 KB Output is correct
11 Correct 16 ms 580 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 14744 KB Output is correct
2 Correct 448 ms 14756 KB Output is correct
3 Correct 677 ms 17808 KB Output is correct
4 Correct 671 ms 17700 KB Output is correct
5 Correct 470 ms 17536 KB Output is correct
6 Correct 464 ms 17696 KB Output is correct
7 Correct 459 ms 17672 KB Output is correct
8 Correct 459 ms 17644 KB Output is correct
9 Correct 465 ms 17900 KB Output is correct
10 Correct 454 ms 17640 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 7600 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 564 KB Output is correct
3 Correct 8 ms 556 KB Output is correct
4 Correct 26 ms 468 KB Output is correct
5 Correct 24 ms 580 KB Output is correct
6 Correct 17 ms 596 KB Output is correct
7 Correct 17 ms 596 KB Output is correct
8 Correct 16 ms 580 KB Output is correct
9 Correct 16 ms 580 KB Output is correct
10 Correct 16 ms 580 KB Output is correct
11 Correct 16 ms 580 KB Output is correct
12 Correct 435 ms 14744 KB Output is correct
13 Correct 448 ms 14756 KB Output is correct
14 Correct 677 ms 17808 KB Output is correct
15 Correct 671 ms 17700 KB Output is correct
16 Correct 470 ms 17536 KB Output is correct
17 Correct 464 ms 17696 KB Output is correct
18 Correct 459 ms 17672 KB Output is correct
19 Correct 459 ms 17644 KB Output is correct
20 Correct 465 ms 17900 KB Output is correct
21 Correct 454 ms 17640 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Incorrect 208 ms 7600 KB Output isn't correct
24 Halted 0 ms 0 KB -