oj.uz

Submission #803377

# Submission time Handle Problem Language Result Execution time Memory
803377 2023-08-03T04:21:14 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
5 / 25
 3034 ms 14876 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;
using mi=modnum<mod>;
ll pw[M];
int n,q;
map<pll,int> S[M][M];
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++;
		S[a][b][{x%pw[a],y%pw[b]}]+=v;
	}
	for(int t=1;t<=q;t++){
		ll x,y; int ans=0;
		cin>>x>>y;
		int a=0,b=0;
		while(pw[a+1]<=x) a++;
		while(pw[b+1]<=y) b++;
		for(int i=0;i<=a;i++) for(int j=0;j<=0;j++){
			pll d={x%pw[i],y%pw[j]};
			if(S[i][j].count(d)) ans+=S[i][j][d];
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 14372 KB Output is correct
2 Correct 761 ms 14876 KB Output is correct
3 Correct 2958 ms 12896 KB Output is correct
4 Correct 3034 ms 13052 KB Output is correct
5 Correct 1410 ms 12824 KB Output is correct
6 Correct 1827 ms 12816 KB Output is correct
7 Correct 1744 ms 12736 KB Output is correct
8 Correct 1539 ms 12712 KB Output is correct
9 Correct 1439 ms 12824 KB Output is correct
10 Correct 1433 ms 12748 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -