oj.uz

답안 #803364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
803364 2023-08-03T04:18:05 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 1039036 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++){
			ans+=S[i][j][{x%pw[i],y%pw[j]}];
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1392 ms 278764 KB Output is correct
3 Correct 1449 ms 279056 KB Output is correct
4 Correct 2725 ms 442932 KB Output is correct
5 Correct 2700 ms 443016 KB Output is correct
6 Correct 615 ms 112420 KB Output is correct
7 Correct 581 ms 109964 KB Output is correct
8 Correct 573 ms 109772 KB Output is correct
9 Correct 554 ms 108016 KB Output is correct
10 Correct 546 ms 109900 KB Output is correct
11 Correct 604 ms 113296 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4086 ms 1039036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Execution timed out 4066 ms 610996 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1392 ms 278764 KB Output is correct
3 Correct 1449 ms 279056 KB Output is correct
4 Correct 2725 ms 442932 KB Output is correct
5 Correct 2700 ms 443016 KB Output is correct
6 Correct 615 ms 112420 KB Output is correct
7 Correct 581 ms 109964 KB Output is correct
8 Correct 573 ms 109772 KB Output is correct
9 Correct 554 ms 108016 KB Output is correct
10 Correct 546 ms 109900 KB Output is correct
11 Correct 604 ms 113296 KB Output is correct
12 Execution timed out 4086 ms 1039036 KB Time limit exceeded
13 Halted 0 ms 0 KB -