Submission #28144

#	Time	Username	Problem	Language	Result	Execution time	Memory
28144		asd (#71)	The City and The Bitcoin (FXCUP2_city)	C++14	0 / 1	0 ms	8692 KiB

city

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()

#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define INF 987654321
#define IINF 987654321987654321
#define MAXV 3000500


#define MOD 1234567

int N,M,T,K;

vector<int> plist[100500];
int p[100500];
int cnt[1000500];
int Bsize;

struct query{
	int l,r,n;
};

bool cmp(query& a, query& b){
	if( a.l/Bsize == b.l/Bsize ) return a.r < b.r;
	else return a.l/Bsize < b.l/Bsize;
}

void init(){
	rep(i,100500) plist[i].clear();
	memset(cnt,0,sizeof cnt);
}

vector<int> getp(int n){
	vector<int> res;
	for(int i=1;i*i<=n;i++){
		if( n%i == 0 ){
			if( i*i == n ) res.pb(i);
			else{
				res.pb(i);
				res.pb(n/i);
			}
		}
	}
	return res;
}

void solve(){
	init();
	geti(N,M);
	repp(i,N) geti(p[i]);

	repp(j,N){
		int n = p[j];
		for(int i=1;i*i<=n;i++){
			if( n%i == 0 ){
				if( i*i == n ) plist[j].pb(i);
				else{
					plist[j].pb(i);
					plist[j].pb(n/i);
				}
			}
		}
	}
	vector<query> q;

	repp(i,M){
		int a,b,c; geti(a,b,c);
		q.push_back({b,c,a});
	}

	Bsize = (int) sqrt(1.0*N);
	sort(all(q),cmp);
	int ans = 0;
	int l=1, r=0; int sum = 0;
	for(int i=0;i<q.size();i++){
		sum = 0;
		query& e = q[i];
		int ql = e.l, qr = e.r;
		while( r < qr ){
			r++;
			//sum += p[r]*(2*c[p[r]]+1); cnt[p[r]]++;
			for(auto x : plist[r]) cnt[x]++;
		}
		while( r > qr ){
			//sum += p[r]*(1-2*c[p[r]]); cnt[p[r]]--;
			for(auto x : plist[r]) cnt[x]--;
			r--;
		}
		while( l < ql ){
			//sum += p[l]*(1-2*c[p[l]]); cnt[p[l]]--;
			for(auto x : plist[l]) cnt[x]--;
			l++;
		}
		while( l > ql ){
			l--;
			for(auto x : plist[l]) cnt[x]++;
			//sum += p[l]*(2*c[p[l]]+1); cnt[p[l]]++;
		}

		int n = e.n;

		for(int x=1;x*x<=n;x++){
			if( n%x == 0 ){
				if( x*x == n ){
					if( cnt[x] == 0 ) sum++;
				}
				else{
					if( cnt[x] == 0 ) sum++;
					if( cnt[n/x] == 0 ) sum++;
				}
			}
		}
		/*
		vector<int> v = getp(n);

		for(auto e : v){
			if( cnt[e] == 0 ) sum++;
		}
		*/
		ans += sum;
	}
	
	printf("%d\n",ans);
}

#include <ctime>

int main(){
	clock_t begin = clock();
	setbuf(stdout,NULL);
	int tc; scanf("%d",&tc);
	repp(t,tc){
		printf("Case #%d\n",t);
		solve();
	}
	clock_t end = clock();
	double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
	cout << elapsed_secs << endl;
}

Compilation message (stderr)

city.cpp: In function 'void solve()':
city.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<q.size();i++){
               ^
city.cpp:83:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  geti(N,M);
           ^
city.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  repp(i,N) geti(p[i]);
                      ^
city.cpp:101:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c; geti(a,b,c);
                         ^
city.cpp: In function 'int main()':
city.cpp:165:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int tc; scanf("%d",&tc);
                         ^

• Subtask 1: 0 / 1