Submission #1012957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012957		vjudge1	Meteors (POI11_met)	C++14	100 / 100	781 ms	45140 KiB

met

#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int N = 6e5 + 10, inf = 0x3f3f3f3f;
int n,m,k,p[N];
int q[N],ql[N],qr[N],ans[N];
struct Bit{
	int c[N];
	#define lowbit(a) ((a)&(-a))
	void add(int x,int v){ for(int i = x;i<=m;i += lowbit(i))c[i] += v; }
	int query(int x){ int res = 0; for(int i = x;i;i -= lowbit(i))res += c[i]; return res; }
}tr;
struct P{ int l,r,val; }e[N];
vector<int> ji[N];
int cnt[N];
void solve(int l,int r,int x,int y){
	if(l == r){ for(int i = x;i<=y;++i)ans[q[i]] = l; return ; }
	int mid = l + r >> 1, top1 = 0, top2 = 0;
	for(int i = l;i<=mid;++i)
		tr.add(e[i].l,e[i].val),tr.add(e[i].r+1,-e[i].val);
	for(int i = x;i<=y;++i){
        int now = 0;
        for(int z : ji[q[i]]){
        	now += tr.query(z);
        	if(now >= p[q[i]])break;
		}
        if(now >= p[q[i]])ql[++top1] = q[i];
        else qr[++top2] = q[i],p[q[i]] -= now;
    }
	for(int i = l;i<=mid;++i)
		tr.add(e[i].l,-e[i].val),tr.add(e[i].r+1,e[i].val);
	for(int i = x;i<=x+top1-1;++i)q[i] = ql[i-x+1];
	for(int i = x+top1;i<=x+top1+top2-1;++i)q[i] = qr[i-x-top1+1];
	solve(l,mid,x,x+top1-1), solve(mid+1,r,x+top1,x+top1+top2-1);
}

signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i = 1,x;i<=m;++i){
		scanf("%lld",&x);
		ji[x].push_back(i),ji[x].push_back(i+m);
	}
	m <<= 1;
	for(int i = 1;i<=n;++i)scanf("%lld",&p[i]);
	scanf("%lld",&k);
	for(int i = 1;i<=k;++i){
		scanf("%lld%lld%lld",&e[i].l,&e[i].r,&e[i].val);
		if(e[i].r < e[i].l)e[i].r += (m>>1);
	}
	for(int i = 1;i<=n;++i)q[i] = i;
	e[++k] = {1,n,inf};
	solve(1,k,1,n);
	for(int i = 1;i<=n;++i){
		if(ans[i] == k)puts("NIE");
		else printf("%lld\n",ans[i]);
	}
    return 0;
}

Compilation message (stderr)

met.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
met.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid = l + r >> 1, top1 = 0, top2 = 0;
      |            ~~^~~
met.cpp: In function 'int main()':
met.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%lld%lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%lld",&x);
      |   ~~~~~^~~~~~~~~~~
met.cpp:46:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  for(int i = 1;i<=n;++i)scanf("%lld",&p[i]);
      |                         ~~~~~^~~~~~~~~~~~~~
met.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%lld",&k);
      |  ~~~~~^~~~~~~~~~~
met.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%lld%lld%lld",&e[i].l,&e[i].r,&e[i].val);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13