oj.uz

Submission #535698

# Submission time Handle Problem Language Result Execution time Memory
535698 2022-03-11T00:15:21 Z colazcy Poklon (COCI17_poklon) C++17
140 / 140
 618 ms 104284 KB 
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 5e5 + 100;

int n,q,val[maxn],ans[maxn];
std::vector<int> pos[maxn];
void discretize(){
	static int tmp[maxn];
	std::copy_n(val + 1,n,tmp + 1);
	std::sort(tmp + 1,tmp + 1 + n);
	let tot = std::unique(tmp + 1,tmp + 1 + n) - tmp - 1;
	rep(i,1,n)val[i] = std::lower_bound(tmp + 1,tmp + 1 + tot,val[i]) - tmp;
}
namespace fenwick{
	int f[maxn];
	constexpr int lowbit(const int x){return x & (-x);}
	void add(int pos,const int v){
		for(;pos <= n;pos += lowbit(pos))f[pos] += v;
	}
	int query(int pos){
		int res = 0;
		for(;pos;pos -= lowbit(pos))res += f[pos];
		return res;
	}
}
struct Event{int opt,id,x,y,v;};
std::vector<Event> events;
void ins(const int lx,const int rx,const int ly,const int ry){
	events.push_back(Event{1,0,lx,ly,1});
	events.push_back(Event{1,0,rx + 1,ly,-1});
	events.push_back(Event{1,0,lx,ry + 1,-1});
	events.push_back(Event{1,0,rx + 1,ry + 1,1});	
}

int main(){
	// std::freopen("poklon.in","r",stdin);
	// std::freopen("poklon.out","w",stdout);
	std::scanf("%d %d",&n,&q);
	rep(i,1,n)std::scanf("%d",val + i);	
	discretize();
	rep(i,1,n)pos[val[i]].push_back(i);	
	rep(v,1,n){
		let &pos = ::pos[v];
		for(size_t i = 1;i < pos.size();i++){
			let p = pos[i - 1],q = pos[i];
			let pre = i == 1 ? 1 : pos[i - 2] + 1;
			let nxt = i + 1 == pos.size() ? n : pos[i + 1] - 1;
			ins(pre,p,q,nxt);
		}
	}
	rep(id,1,q){
		int l,r; std::scanf("%d %d",&l,&r);
		events.push_back(Event{0,id,l,r,0});
	}
	std::sort(events.begin(),events.end(),[](const Event &a,const Event &b){
		if(a.x != b.x)return a.x < b.x;
		return a.opt > b.opt;
	});
	for(let &e : events)
		if(e.opt == 1)fenwick::add(e.y,e.v);
		else ans[e.id] = fenwick::query(e.y);
	rep(i,1,q)std::printf("%d\n",ans[i]);
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:46:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  std::scanf("%d %d",&n,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~
poklon.cpp:47:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  rep(i,1,n)std::scanf("%d",val + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
poklon.cpp:60:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   int l,r; std::scanf("%d %d",&l,&r);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12244 KB Output is correct
4 Correct 11 ms 12944 KB Output is correct
5 Correct 108 ms 25616 KB Output is correct
6 Correct 109 ms 25700 KB Output is correct
7 Correct 235 ms 39616 KB Output is correct
8 Correct 373 ms 59164 KB Output is correct
9 Correct 469 ms 67748 KB Output is correct
10 Correct 618 ms 104284 KB Output is correct