#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);
struct item {
ll a , b;
};
struct Seg {
vector<item> v;
vector<ll> arr;
vector<ll> neg;
int siz;
item nutral = {0,0};
item merge(item x , item y , ll& negg){
ll a = min(x.b , y.a);
y.a -= a;
negg += a;
x.b -= a;
x.a += y.a;
x.b += y.b;
return x;
}
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
v.assign(siz * 2 , nutral);
arr.assign(siz * 2 , 0);
neg.assign(siz * 2 , 0);
}
pair<ll,ll> find(int i , int x , int lx , int rx){
if(rx - lx == 1){
arr[x] -= v[x].a;
neg[x] += v[x].a + (arr[x] < 0 ? arr[x] : 0);
arr[x] = max(arr[x] , 0LL);
arr[x] += v[x].b;
v[x] = nutral;
return mp(arr[x],neg[x]);
}
int m = (lx + rx)/2;
v[2 * x + 1] = merge(v[2 * x + 1] , v[x] , neg[2 * x + 1]);
v[2 * x + 2] = merge(v[2 * x + 2] , v[x] , neg[2 * x + 2]);
v[x] = nutral;
neg[2 * x + 1] += neg[x];
neg[2 * x + 2] += neg[x];
neg[x] = 0;
if(i < m){
return find(i , 2 * x + 1 , lx , m);
}
else return find(i , 2 * x + 2 , m , rx);
}
pair<ll,ll> find(int i){
return find(i , 0 , 0 , siz);
}
void range(int l , int r , item it , int x , int lx , int rx){
if(l >= rx || r <= lx)return;
if(lx >= l && rx <= r){
v[x] = merge(v[x] , it , neg[x]);
return;
}
v[2 * x + 1] = merge(v[2 * x + 1] , v[x] , neg[2 * x + 1]);
v[2 * x + 2] = merge(v[2 * x + 2] , v[x] , neg[2 * x + 2]);
v[x] = nutral;
neg[2 * x + 1] += neg[x];
neg[2 * x + 2] += neg[x];
neg[x] = 0;
int m = (lx + rx)/2;
range(l , r , it , 2 * x + 1 , lx , m);
range(l , r , it , 2 * x + 2 , m , rx);
}
void range(int l , int r , item it){
range(l , r , it , 0 , 0 , siz);
}
};
struct Seg2 {
vector<pair<int,ll>> v1;
int siz;
vector<ll> lazy;
vector<ll> mn;
vector<ll> mn1;
ll nutral = 1e18;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
lazy.assign(siz * 2 , 0);
mn.assign(siz * 2 , nutral);
mn1.assign(siz * 2 , nutral);
}
void build(vector<ll>& a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < (int)a.size()){
mn[x] = a[lx];
mn1[x] = a[lx];
}
return;
}
int m = (lx + rx)/2;
build(a , 2 * x + 1 , lx , m);
build(a , 2 * x + 2 , m , rx);
mn1[x] = min(mn1[2 * x + 1] , mn1[2 * x + 2]);
}
void build(vector<ll>& a){
build(a,0,0,siz);
}
void set(int i , ll v , int x , int lx, int rx){
if(rx - lx == 1){
mn[x] = v;
mn1[x] = v - lazy[x];
return;
}
ll tp = lazy[x];
lazy[2 * x + 1] += lazy[x];
lazy[2 * x + 2] += lazy[x];
lazy[x] = 0;
int m = (lx + rx)/2;
if(i < m){
set(i , v , 2 * x + 1 , lx , m);
mn1[x] = min(mn1[2 * x + 1] , mn1[2 * x + 2] - tp);
}
else {
set(i , v , 2 * x + 2 , m , rx);
mn1[x] = min(mn1[2 * x + 1] - tp , mn1[2 * x + 2]);
}
}
void set(int i , ll v){
set(i , v , 0 , 0 , siz);
}
void range(int l , int r , ll v , int x , int lx, int rx){
if(rx - lx > 1){
lazy[2 * x + 1] += lazy[x];
lazy[2 * x + 2] += lazy[x];
mn1[x] -= lazy[x];
lazy[x] = 0;
}
if(l >= rx || lx >= r){
return;
}
if(rx - lx == 1){
lazy[x] += v;
mn1[x] -= v;
if(lazy[x] >= mn[x]){
v1.pb(mp(lx,lazy[x]));
}
return;
}
if(lx >= l && rx <= r && v < mn1[x]){
lazy[2 * x + 1] += v;
lazy[2 * x + 2] += v;
mn1[x] -= v;
return;
}
int m = (lx + rx)/2;;
range(l , r , v , 2 * x + 1 , lx , m);
range(l , r , v , 2 * x + 2 , m , rx);
mn1[x] = min(mn1[2 *x + 1] , mn1[2 * x + 2]);
}
void range(int l , int r , ll v){
v1.clear();
range(l , r , v , 0 , 0 , siz);
}
};
void solve(){
int n , m , q;
cin >> n >> m >> q;
Seg st;
st.init(n);
item it;
int ans[q];
vector<pair<ll,int>> v[n];
for(int i = 0; i < n; i++){
v[i].pb(mp(1e18 , 1e9));
}
vector<pair<pair<int,int> , pair<int,int>>> queries;
for(int i = 0; i < q; i++){
int ti;
cin >> ti;
if(ti == 1){
int l , r, c , k;
cin >> l >> r >> c >> k;
it.a = 0;
it.b = k;
st.range(l-1 , r , it);
ans[i] = -1;
queries.pb(mp(mp(l-1 , r) , mp(c, k)));
}
else if(ti == 2){
int l , r , k;
cin >> l >> r >> k;
it.a = k;
it.b = 0;
st.range(l -1 , r , it);
ans[i] = -1;
}
else {
ll a , b;
cin >> a >> b;
pair<ll,ll> x = st.find(a-1);
if(x.vf >= b){
v[a-1].pb(mp(b + x.vs , i));
ans[i] = -2;
}
else ans[i] = 0;
}
}
int pos[n];
memset(pos , 0 , sizeof pos);
vector<ll> a(n);
for(int i = 0; i < n; i++){
sv(v[i]);
a[i] = v[i][0].vf;
}
Seg2 st2;
st2.init(n);
st2.build(a);
for(auto i : queries){
st2.range(i.vf.vf , i.vf.vs , i.vs.vs);
for(auto j : st2.v1){
while(v[j.vf][pos[j.vf]].vf <= j.vs){
ans[v[j.vf][pos[j.vf]].vs] = i.vs.vf;
pos[j.vf]++;
}
st2.set(j.vf , v[j.vf][pos[j.vf]].vf);
}
}
for(int i = 0; i < q; i++){
if(ans[i] != -1)
cout << ans[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while(t--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
13724 KB |
Output is correct |
| 2 |
Incorrect |
78 ms |
13968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
461 ms |
49808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
