oj.uz

Submission #1012957

# Submission time Handle Problem Language Result Execution time Memory
1012957 2024-07-03T02:54:49 Z vjudge1 Meteors (POI11_met) C++14
100 / 100
 781 ms 45140 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16216 KB Output is correct
2 Correct 5 ms 16220 KB Output is correct
3 Correct 5 ms 16220 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16220 KB Output is correct
2 Correct 6 ms 16220 KB Output is correct
3 Correct 5 ms 16220 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19288 KB Output is correct
2 Correct 85 ms 20312 KB Output is correct
3 Correct 67 ms 19780 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19548 KB Output is correct
2 Correct 59 ms 19544 KB Output is correct
3 Correct 72 ms 20304 KB Output is correct
4 Correct 24 ms 18264 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19124 KB Output is correct
2 Correct 59 ms 19924 KB Output is correct
3 Correct 23 ms 17240 KB Output is correct
4 Correct 60 ms 19804 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 19152 KB Output is correct
2 Correct 54 ms 19500 KB Output is correct
3 Correct 52 ms 19288 KB Output is correct
4 Correct 72 ms 20308 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 40428 KB Output is correct
2 Correct 327 ms 37436 KB Output is correct
3 Correct 113 ms 21840 KB Output is correct
4 Correct 781 ms 43604 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 39512 KB Output is correct
2 Correct 689 ms 30408 KB Output is correct
3 Correct 107 ms 20816 KB Output is correct
4 Correct 781 ms 45140 KB Output is correct