oj.uz

Submission #870039

# Submission time Handle Problem Language Result Execution time Memory
870039 2023-11-06T17:33:02 Z LOLOLO Meteors (POI11_met) C++14
74 / 100
 848 ms 37464 KB 
#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
const int MOD = 1e9+7;

typedef long long ll;
typedef pair<int,int> pii;

int m;
const int MAXN = 3e5+5;
ll BIT[MAXN];
vector<int> mid[MAXN],mem[MAXN];
int reqd[MAXN];
int x[MAXN],y[MAXN],z[MAXN];
int ans[MAXN];
int l[MAXN],r[MAXN];
void update(int idx, int val) {
	while(idx<=m) {
		BIT[idx]+=1LL*val;
		idx+=(idx&-idx);
	}
}
ll query(int idx) {
	ll ret=0;
	while(idx) {
		ret+=BIT[idx];
		idx-=(idx&-idx);
	}
	return ret;
}
int main() {
	// freopen("TASK.in","r",stdin);	
	// freopen("TASK.out","w",stdout);
	int n;
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x;
		scanf("%d",&x);
		mem[x].pb(i);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&reqd[i]);
	int q;
	cin>>q;
	for(int i=1;i<=q;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
	for(int i=1;i<=n;i++) l[i]=1,r[i]=q,ans[i]=-1;
	bool changed=true;
	while(changed) {
		changed=false;
		for(int i=0;i<=q;i++) mid[i].clear();
		for(int i=0;i<=m;i++) BIT[i]=0;
		for(int i=1;i<=n;i++) {
			if(l[i]<=r[i]) {
				mid[l[i]+(r[i]-l[i]+1)/2].pb(i);
			}
		}
		for(int i=1;i<=q;i++) {
			if(x[i]<=y[i]) {
				update(x[i],z[i]);
				update(y[i]+1,-z[i]);
			}
			else {
				update(x[i],z[i]);
				update(1,z[i]);
				update(y[i]+1,-z[i]);
			}
			for(auto it:mid[i]) {
				changed=true;
				ll qu=0;
				for(auto j:mem[it]) qu+=query(j);
				if(qu>=reqd[it]) {
					ans[it]=i;
					r[it]=i-1;
				}
				else l[it]=i+1;
			}
		}
	}
	for(int i=1;i<=n;i++) if(ans[i]==-1) printf("NIE\n");else printf("%d\n",ans[i]);
	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
met.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d",&reqd[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
met.cpp:52:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  for(int i=1;i<=q;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23656 KB Output is correct
2 Correct 96 ms 25424 KB Output is correct
3 Correct 74 ms 25172 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 24696 KB Output is correct
2 Correct 82 ms 24976 KB Output is correct
3 Correct 97 ms 25644 KB Output is correct
4 Correct 25 ms 24400 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 24144 KB Output is correct
2 Correct 70 ms 26148 KB Output is correct
3 Correct 42 ms 23124 KB Output is correct
4 Correct 81 ms 25428 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 23332 KB Output is correct
2 Correct 79 ms 24704 KB Output is correct
3 Correct 55 ms 23388 KB Output is correct
4 Correct 104 ms 26880 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 37464 KB Output is correct
2 Incorrect 617 ms 26200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 36264 KB Output is correct
2 Incorrect 685 ms 26428 KB Output isn't correct
3 Halted 0 ms 0 KB -