oj.uz

Submission #803370

# Submission time Handle Problem Language Result Execution time Memory
803370 2023-08-03T04:19:54 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 13596 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<=b;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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 131 ms 648 KB Output is correct
3 Correct 130 ms 652 KB Output is correct
4 Correct 133 ms 656 KB Output is correct
5 Correct 134 ms 660 KB Output is correct
6 Correct 32 ms 660 KB Output is correct
7 Correct 32 ms 656 KB Output is correct
8 Correct 31 ms 664 KB Output is correct
9 Correct 31 ms 596 KB Output is correct
10 Correct 31 ms 596 KB Output is correct
11 Correct 32 ms 596 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 13596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1397 ms 7376 KB Output is correct
3 Correct 1381 ms 7564 KB Output is correct
4 Execution timed out 4003 ms 6864 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 131 ms 648 KB Output is correct
3 Correct 130 ms 652 KB Output is correct
4 Correct 133 ms 656 KB Output is correct
5 Correct 134 ms 660 KB Output is correct
6 Correct 32 ms 660 KB Output is correct
7 Correct 32 ms 656 KB Output is correct
8 Correct 31 ms 664 KB Output is correct
9 Correct 31 ms 596 KB Output is correct
10 Correct 31 ms 596 KB Output is correct
11 Correct 32 ms 596 KB Output is correct
12 Execution timed out 4043 ms 13596 KB Time limit exceeded
13 Halted 0 ms 0 KB -