oj.uz

답안 #803627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
803627 2023-08-03T05:10:11 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
15 / 25
 4000 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;
			if(i>k){
				p++;
				continue;
			}
			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++;
			int 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 556 KB Output is correct
3 Correct 9 ms 468 KB Output is correct
4 Correct 26 ms 560 KB Output is correct
5 Correct 25 ms 584 KB Output is correct
6 Correct 16 ms 596 KB Output is correct
7 Correct 18 ms 564 KB Output is correct
8 Correct 16 ms 468 KB Output is correct
9 Correct 17 ms 584 KB Output is correct
10 Correct 18 ms 468 KB Output is correct
11 Correct 16 ms 580 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 481 ms 14880 KB Output is correct
2 Correct 472 ms 14744 KB Output is correct
3 Correct 660 ms 17768 KB Output is correct
4 Correct 668 ms 17700 KB Output is correct
5 Correct 456 ms 17512 KB Output is correct
6 Correct 472 ms 17792 KB Output is correct
7 Correct 454 ms 17620 KB Output is correct
8 Correct 461 ms 17640 KB Output is correct
9 Correct 472 ms 17900 KB Output is correct
10 Correct 453 ms 17644 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 209 ms 7616 KB Output is correct
3 Correct 207 ms 7628 KB Output is correct
4 Correct 1188 ms 9028 KB Output is correct
5 Correct 1205 ms 9292 KB Output is correct
6 Correct 910 ms 9172 KB Output is correct
7 Correct 915 ms 9244 KB Output is correct
8 Correct 925 ms 9108 KB Output is correct
9 Correct 923 ms 9136 KB Output is correct
10 Correct 919 ms 9192 KB Output is correct
11 Correct 907 ms 9320 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 556 KB Output is correct
3 Correct 9 ms 468 KB Output is correct
4 Correct 26 ms 560 KB Output is correct
5 Correct 25 ms 584 KB Output is correct
6 Correct 16 ms 596 KB Output is correct
7 Correct 18 ms 564 KB Output is correct
8 Correct 16 ms 468 KB Output is correct
9 Correct 17 ms 584 KB Output is correct
10 Correct 18 ms 468 KB Output is correct
11 Correct 16 ms 580 KB Output is correct
12 Correct 481 ms 14880 KB Output is correct
13 Correct 472 ms 14744 KB Output is correct
14 Correct 660 ms 17768 KB Output is correct
15 Correct 668 ms 17700 KB Output is correct
16 Correct 456 ms 17512 KB Output is correct
17 Correct 472 ms 17792 KB Output is correct
18 Correct 454 ms 17620 KB Output is correct
19 Correct 461 ms 17640 KB Output is correct
20 Correct 472 ms 17900 KB Output is correct
21 Correct 453 ms 17644 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 209 ms 7616 KB Output is correct
24 Correct 207 ms 7628 KB Output is correct
25 Correct 1188 ms 9028 KB Output is correct
26 Correct 1205 ms 9292 KB Output is correct
27 Correct 910 ms 9172 KB Output is correct
28 Correct 915 ms 9244 KB Output is correct
29 Correct 925 ms 9108 KB Output is correct
30 Correct 923 ms 9136 KB Output is correct
31 Correct 919 ms 9192 KB Output is correct
32 Correct 907 ms 9320 KB Output is correct
33 Correct 764 ms 15828 KB Output is correct
34 Correct 755 ms 15900 KB Output is correct
35 Execution timed out 4038 ms 16560 KB Time limit exceeded
36 Halted 0 ms 0 KB -