oj.uz

답안 #1012956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012956 2024-07-03T02:47:38 Z vjudge1 Meteors (POI11_met) C++14
100 / 100
 592 ms 65536 KB 
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=3e5+10;
int n,m,t,tot;
int a[N],p[N],ans[N];
ll sum[N];
struct Modify{
	int x,t,v;
	friend bool operator <(Modify a,Modify b){
		return a.x<b.x;
	}
};
#define mid (l+r>>1)
void Bound(int l,int r,vector<Modify> &mo,vector<int> &vec){
	for(const int &x:vec)sum[a[x]]=0;
	if(l==r){
		int it=0;
		ll Sum=0;
		for(const int &x:vec){
			for(;it<mo.size()&&mo[it].x<=x;++it)Sum+=mo[it].v;
			if(sum[a[x]]<p[a[x]])sum[a[x]]+=Sum;
		}
		for(const int &x:vec)ans[a[x]]=(sum[a[x]]>=p[a[x]]?l:-1);
		return mo.clear(),vec.clear();
	}
	vector<Modify> Ls,Rs;
	vector<int> ls,rs;
	for(const Modify &x:mo)(x.t<=mid?Ls:Rs).push_back(x);
	mo.clear();
	int it=0;
	ll Sum=0;
	for(const int &x:vec){
		for(;it<Ls.size()&&Ls[it].x<=x;++it)Sum+=Ls[it].v;
		if(sum[a[x]]<p[a[x]])sum[a[x]]+=Sum;
	}
	for(const int &x:vec)(sum[a[x]]>=p[a[x]]?ls:rs).push_back(x);
	vec.clear();
	for(const int &x:rs)if(~sum[a[x]])p[a[x]]-=sum[a[x]],sum[a[x]]=-1;
	Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
}
#undef mid
signed main(){
	cin>>n>>m;
	FOR(i,1,m)cin>>a[i];
	FOR(i,1,n)cin>>p[i],ans[i]=-1;
	vector<int> vec(m);
	vector<Modify> mo;
	cin>>t;
	FOR(i,1,t){
		int l,r,a;cin>>l>>r>>a,++r;
		if(l<r){
			mo.push_back({l,i,a});
			if(r<=m)mo.push_back({r,i,-a});
		}else{
			mo.push_back({1,i,a});
			if(l^r)mo.push_back({r,i,-a}),mo.push_back({l,i,a});
		}
	}
	iota(vec.begin(),vec.end(),1),sort(mo.begin(),mo.end());
	Bound(1,t,mo,vec);
	FOR(i,1,n){
		if(~ans[i])cout<<ans[i]<<endl;
		else cout<<"NIE"<<endl;
	}
	return 0;
}

Compilation message

met.cpp: In function 'void Bound(int, int, std::vector<Modify>&, std::vector<int>&)':
met.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modify>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(;it<mo.size()&&mo[it].x<=x;++it)Sum+=mo[it].v;
      |         ~~^~~~~~~~~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 | #define mid (l+r>>1)
      |              ~^~
met.cpp:39:31: note: in expansion of macro 'mid'
   39 |  for(const Modify &x:mo)(x.t<=mid?Ls:Rs).push_back(x);
      |                               ^~~
met.cpp:44:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modify>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(;it<Ls.size()&&Ls[it].x<=x;++it)Sum+=Ls[it].v;
      |        ~~^~~~~~~~~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 | #define mid (l+r>>1)
      |              ~^~
met.cpp:50:10: note: in expansion of macro 'mid'
   50 |  Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
      |          ^~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 | #define mid (l+r>>1)
      |              ~^~
met.cpp:50:27: note: in expansion of macro 'mid'
   50 |  Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
      |                           ^~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2524 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 10188 KB Output is correct
2 Correct 72 ms 13820 KB Output is correct
3 Correct 63 ms 8764 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 9164 KB Output is correct
2 Correct 58 ms 9092 KB Output is correct
3 Correct 69 ms 14016 KB Output is correct
4 Correct 31 ms 5356 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 8656 KB Output is correct
2 Correct 65 ms 12484 KB Output is correct
3 Correct 36 ms 7628 KB Output is correct
4 Correct 64 ms 8760 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 13652 KB Output is correct
2 Correct 60 ms 11456 KB Output is correct
3 Correct 46 ms 9232 KB Output is correct
4 Correct 94 ms 11908 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 406 ms 58720 KB Output is correct
2 Correct 244 ms 65536 KB Output is correct
3 Correct 153 ms 31988 KB Output is correct
4 Correct 535 ms 49984 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 56500 KB Output is correct
2 Correct 193 ms 46244 KB Output is correct
3 Correct 134 ms 23768 KB Output is correct
4 Correct 592 ms 52960 KB Output is correct