oj.uz

Submission #284561

# Submission time Handle Problem Language Result Execution time Memory
284561 2020-08-27T16:11:05 Z limabeans Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 93 ms 5848 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

template<typename T> struct segtree {
    
    T merge(T x, T y) {
	x += y;
	return x;
    }
    int n;
    vector<ll> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void upd(int v, int tl, int tr, int i, T val) {
	if (tl == tr) {
	    t[v] = val;
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,val);
	    } else {
		upd(2*v+1,tm+1,tr,i,val);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return 0;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};

int n, q, k;
int a[maxn];
int S[maxn], T[maxn], U[maxn];

void brute(int type, int t, int u, ll& res) {
    if (type==1) {
	int idx = t;
	int val = u;
	a[idx] = val;
    }
    if (type==2) {
	int l = t;
	int r = u;
	for (int i=l; i<=r; i++) {
	    a[i] /= k;
	}
    }
    if (type==3) {
	res = 0;
	int l = t;
	int r = u;
	for (int i=l; i<=r; i++) {
	    res += a[i];
	}
    }
}


void solveTask1() {
    for (int i=0; i<q; i++) {
	int s = S[i];
	int t = T[i];
	int u = U[i];
	ll bans=-1; brute(s,t,u,bans);
	if (s==3) cout<<bans<<"\n";
    }
}

// Task2 on oj.uz
void solveTask2() {
    segtree<ll> tree;
    tree.init(n+10);
    for (int i=1; i<=n; i++) {
	tree.upd(1,1,n,i,a[i]);
    }
    for (int i=0; i<q; i++) {
	if (S[i]==1) {
	    tree.upd(1,1,n,T[i],U[i]);
	}
	if (S[i]==3) {
	    cout<<tree.qry(1,1,n,T[i],U[i])<<"\n";
	}
    }
}

//////////////////////////////////////////////////////////////////
ll t[maxn];
bool marked[maxn];

void push(int v) {
    if (marked[v]) {
	t[v*2]=t[2*v+1]=t[v];
	marked[v*2]=marked[2*v+1]=true;
	marked[v]=false;
    }
}

ll queryRange(int v, int tl, int tr, int l, int r) {
    if (r<tl || tr<l) return 0;
    if (l<=tl && tr<=r) return t[v];
    push(v);
    int tm=(tl+tr)/2;
    return queryRange(2*v,tl,tm,l,r)+queryRange(2*v+1,tm+1,tr,l,r);
}

void setRange(int v, int tl, int tr, int l, int r, int val) {
    if (l>r) return;
    if (l==tl && tr==r) {
	t[v]=val;
	marked[v]=true;
	return;
    }
    push(v);
    int tm=(tl+tr)/2;
    setRange(2*v,tl,tm,l,min(tm,r),val);
    setRange(2*v+1,tm+1,tr,max(tm+1,l),r,val);
}
//////////////////////////////////////////////////////////////////

void solveTask3() {
    //cout<<"Task3"<<endl;
    for (int i=1; i<=n; i++) {
	setRange(1,1,n,i,i,a[i]);
    }
    for (int i=0; i<q; i++) {
	if (S[i]==1) {
	    setRange(1,1,n,T[i],T[i],U[i]);
	}
	if (S[i]==2) {
	    if (k>1) {
		setRange(1,1,n,T[i],U[i],0);
	    }
	}
	if (S[i]==3) {
	    cout<<queryRange(1,1,n,T[i],U[i])<<"\n";
	}
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q>>k;
    bool isTask3 = true;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
	if (!(0<=a[i] && a[i]<=1)) isTask3=false;
    }
    for (int i=0; i<q; i++) {
	cin>>S[i]>>T[i]>>U[i];
	if (S[i]==1) {
	    if (!(0<=U[i] && U[i]<=1)) isTask3=false;
	}
    }

    if (k==1) {
	solveTask2();
	exit(0);
    }

    if (isTask3) {
	solveTask3();
	exit(0);
    }

    if (n<=3000 && q<=3000) {
	solveTask1();
	exit(0);
    }

    
    assert(false);
    
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 8 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 7 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4216 KB Output is correct
2 Correct 50 ms 3448 KB Output is correct
3 Correct 51 ms 4600 KB Output is correct
4 Correct 71 ms 5652 KB Output is correct
5 Correct 77 ms 5752 KB Output is correct
6 Correct 76 ms 5752 KB Output is correct
7 Correct 75 ms 5752 KB Output is correct
8 Correct 75 ms 5752 KB Output is correct
9 Correct 72 ms 5752 KB Output is correct
10 Correct 71 ms 5752 KB Output is correct
11 Correct 75 ms 5848 KB Output is correct
12 Correct 93 ms 5756 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 3064 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -