oj.uz

Submission #143196

# Submission time Handle Problem Language Result Execution time Memory
143196 2019-08-13T10:24:08 Z cheetose Worst Reporter 3 (JOI18_worst_reporter3) C++11
100 / 100
 713 ms 74304 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int a[500001];
int cnt[35][500001];
Vi vv;
int main() {
	int n,q;
	scanf("%d%d",&n,&q);
	scanf("%d",&a[1]);
	vv.pb(a[1]);
	fup(i,2,n,1)
	{
		scanf("%d",a+i);
		a[i]=((a[i]-1)/a[i-1]+1)*a[i-1];
		vv.pb(a[i]);
	}
	sort(ALL(vv));
	vv.resize(unique(ALL(vv))-vv.begin());
	int N=vv.size();
	for(int i=1,t=0;i<=n;i++)
	{
		if(i>1&&a[i]!=a[i-1])t++;
		cnt[t][i]++;
	}
	fup(i,0,N-1,1)fup(j,1,n,1)cnt[i][j]+=cnt[i][j-1];
	while(q--)
	{
		int ans=0;
		int t,l,r;
		scanf("%d%d%d",&t,&l,&r);
		if(t>=l && t<=r)ans++;
		fup(i,0,N-1,1)
		{
			int x=vv[i];
			int y=(t/x)*x;
			int L=y-r,R=y-l;
			if(R<=0 || L>n)continue;
			L=max(1,L),R=min(n,R);
			ans+=cnt[i][R]-cnt[i][L-1];
		}
		printf("%d\n",ans);
	}
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&a[1]);
  ~~~~~^~~~~~~~~~~~
worst_reporter3.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+i);
   ~~~~~^~~~~~~~~~
worst_reporter3.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 24864 KB Output is correct
2 Correct 419 ms 24788 KB Output is correct
3 Correct 422 ms 24768 KB Output is correct
4 Correct 424 ms 24872 KB Output is correct
5 Correct 420 ms 24776 KB Output is correct
6 Correct 424 ms 24808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 508 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 24864 KB Output is correct
2 Correct 419 ms 24788 KB Output is correct
3 Correct 422 ms 24768 KB Output is correct
4 Correct 424 ms 24872 KB Output is correct
5 Correct 420 ms 24776 KB Output is correct
6 Correct 424 ms 24808 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 508 KB Output is correct
13 Correct 409 ms 27168 KB Output is correct
14 Correct 445 ms 27820 KB Output is correct
15 Correct 383 ms 24448 KB Output is correct
16 Correct 400 ms 26972 KB Output is correct
17 Correct 580 ms 66428 KB Output is correct
18 Correct 564 ms 64616 KB Output is correct
19 Correct 613 ms 68860 KB Output is correct
20 Correct 570 ms 66472 KB Output is correct
21 Correct 559 ms 64596 KB Output is correct
22 Correct 565 ms 64600 KB Output is correct
23 Correct 564 ms 64484 KB Output is correct
24 Correct 557 ms 64612 KB Output is correct
25 Correct 433 ms 26756 KB Output is correct
26 Correct 438 ms 26780 KB Output is correct
27 Correct 713 ms 64088 KB Output is correct
28 Correct 711 ms 74304 KB Output is correct
29 Correct 673 ms 73672 KB Output is correct
30 Correct 691 ms 74020 KB Output is correct
31 Correct 694 ms 72136 KB Output is correct
32 Correct 396 ms 25400 KB Output is correct
33 Correct 3 ms 376 KB Output is correct