oj.uz

Submission #554784

# Submission time Handle Problem Language Result Execution time Memory
554784 2022-04-29T11:49:31 Z cheetose Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 173 ms 10472 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a))
#define MEM_1(a) memset((a),-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define COMPRESS(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin())
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<ld> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 998244353;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 };

ll a[100005],T[100005];
int n,m,k;
void upd(int i,ll k){
	while(i<=n){
		T[i]+=k;
		i+=(i&-i);
	}
}
ll sum(int i){
	ll c=0;
	while(i>0){
		c+=T[i];
		i-=(i&-i);
	}
	return c;
}
int o[100000],x[100000],y[100000];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	fup(i,1,n,1)scanf("%lld",a+i);
	fup(i,0,m-1,1)scanf("%d%d%d",o+i,x+i,y+i);
	set<int> S;
	fup(i,1,n,1){
		if(a[i])S.insert(i);
		upd(i,a[i]);
	}
	fup(i,0,m-1,1){
		if(o[i]==1){
			if(y[i]>0)S.insert(x[i]);
			else if(a[x[i]] && !y[i])S.erase(x[i]);
			ll t=y[i]-a[x[i]];
			upd(x[i],t);
			a[x[i]]=y[i];
		}else if(o[i]==2){
			if(k==1)continue;
			auto it=S.lower_bound(x[i]);
			while(it!=S.end() && *it<=y[i]){
				int j=*it;
				ll nx=a[j]/k;
				upd(j,nx-a[j]);
				a[j]=nx;
				if(!nx)it=S.erase(it);
				else it++;
			}
		}else{
			printf("%lld\n",sum(y[i])-sum(x[i]-1));
		}
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
sterilizing.cpp:62:2: note: in expansion of macro 'fup'
   62 |  fup(i,1,n,1)scanf("%lld",a+i);
      |  ^~~
sterilizing.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
sterilizing.cpp:63:2: note: in expansion of macro 'fup'
   63 |  fup(i,0,m-1,1)scanf("%d%d%d",o+i,x+i,y+i);
      |  ^~~
sterilizing.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
sterilizing.cpp:65:2: note: in expansion of macro 'fup'
   65 |  fup(i,1,n,1){
      |  ^~~
sterilizing.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
sterilizing.cpp:69:2: note: in expansion of macro 'fup'
   69 |  fup(i,0,m-1,1){
      |  ^~~
sterilizing.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:62:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  fup(i,1,n,1)scanf("%lld",a+i);
      |              ~~~~~^~~~~~~~~~~~
sterilizing.cpp:63:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  fup(i,0,m-1,1)scanf("%d%d%d",o+i,x+i,y+i);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 580 KB Output is correct
12 Correct 4 ms 580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4908 KB Output is correct
2 Correct 44 ms 3780 KB Output is correct
3 Correct 48 ms 6164 KB Output is correct
4 Correct 60 ms 7792 KB Output is correct
5 Correct 66 ms 8108 KB Output is correct
6 Correct 67 ms 8140 KB Output is correct
7 Correct 91 ms 8192 KB Output is correct
8 Correct 73 ms 8168 KB Output is correct
9 Correct 72 ms 8140 KB Output is correct
10 Correct 71 ms 8144 KB Output is correct
11 Correct 76 ms 8180 KB Output is correct
12 Correct 83 ms 8160 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 980 KB Output is correct
2 Correct 15 ms 2496 KB Output is correct
3 Correct 18 ms 2764 KB Output is correct
4 Correct 37 ms 3636 KB Output is correct
5 Correct 60 ms 6732 KB Output is correct
6 Correct 53 ms 6836 KB Output is correct
7 Correct 56 ms 6940 KB Output is correct
8 Correct 50 ms 6744 KB Output is correct
9 Correct 50 ms 6692 KB Output is correct
10 Correct 54 ms 6664 KB Output is correct
11 Correct 70 ms 6612 KB Output is correct
12 Correct 49 ms 6648 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4456 KB Output is correct
2 Correct 62 ms 6400 KB Output is correct
3 Correct 75 ms 5016 KB Output is correct
4 Correct 73 ms 5280 KB Output is correct
5 Correct 112 ms 10440 KB Output is correct
6 Correct 110 ms 10432 KB Output is correct
7 Correct 98 ms 10428 KB Output is correct
8 Correct 135 ms 10472 KB Output is correct
9 Correct 109 ms 10284 KB Output is correct
10 Correct 124 ms 10320 KB Output is correct
11 Correct 133 ms 10288 KB Output is correct
12 Correct 173 ms 10316 KB Output is correct