| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 671662 | 2022-12-13T12:43:43 Z | tolbi | 원숭이와 사과 나무 (IZhO12_apple) | C++17 | 46 ms | 12776 KB |
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
using namespace std;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct SegTree{
struct Node{
int val, lnode, rnode, l, r, lazy;
Node():lnode(-1),rnode(-1),val(0),lazy(0){}
};
vector<Node> segtree;
SegTree(){
segtree.push_back(Node());
segtree[0].l=1;
segtree[0].r=1000000;
segtree[0].val=0;
segtree[0].lazy=0;
}
void lyap(int node){
int mid = segtree[node].l+(segtree[node].r-segtree[node].l)/2;
if (segtree[node].lnode==-1){
segtree[node].lnode=segtree.size();
segtree.push_back(Node());
segtree[segtree[node].lnode].l=segtree[node].l;
segtree[segtree[node].lnode].r=mid;
}
}
void ryap(int node){
int mid = segtree[node].l+(segtree[node].r-segtree[node].l)/2;
if (segtree[node].rnode==-1){
segtree[node].rnode=segtree.size();
segtree.push_back(Node());
segtree[segtree[node].rnode].l=mid+1;
segtree[segtree[node].rnode].r=segtree[node].r;
}
}
void dallan(int node){
if (segtree[node].lazy==1){
lyap(node);
ryap(node);
segtree[segtree[node].lnode].lazy=1;
segtree[segtree[node].rnode].lazy=1;
segtree[node].val=segtree[node].r-segtree[node].l+1;
}
segtree[node].lazy=0;
}
int query(int l, int r, int node = 0){
dallan(node);
if (segtree[node].l>=l && segtree[node].r<=r) return segtree[node].val;
if (segtree[node].l>r || segtree[node].r<l) return 0ll;
int rval = 0;
if (segtree[node].lnode!=-1){
rval+=query(l, r, segtree[node].lnode);
}
if (segtree[node].rnode!=-1){
rval+=query(l, r, segtree[node].rnode);
}
return rval;
}
void update(int l, int r, int node = 0) {
dallan(node);
if (segtree[node].l>=l && segtree[node].r<=r){
segtree[node].lazy=1;
dallan(node);
return;
}
if (segtree[node].l>r || segtree[node].r<l) return;
int mid = segtree[node].l+(segtree[node].r-segtree[node].l)/2;
if (mid>=l){
lyap(node);
update(l, r, segtree[node].lnode);
}
if (mid+1<=r){
ryap(node);
update(l, r, segtree[node].rnode);
}
segtree[node].val=0ll;
if (segtree[node].lnode!=-1){
dallan(segtree[node].lnode);
segtree[node].val+=segtree[segtree[node].lnode].val;
}
if (segtree[node].rnode!=-1){
dallan(segtree[node].rnode);
segtree[node].val+=segtree[segtree[node].rnode].val;
}
}
};
int32_t main(){
ios;
int t=1;
int tno = 0;
if (!t) cin>>t;
while (t-(tno++)){
SegTree segtree;
deci(q);
int c = 0;
while (q--){
deci(d);
deci(l);deci(r);
l+=c;
r+=c;
if (d==1){
c=segtree.query(l,r);
cout<<c<<endl;
}
else {
segtree.update(l,r);
}
}
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 0 ms | 212 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 17 ms | 6548 KB | Output is correct |
| 5 | Correct | 23 ms | 6648 KB | Output is correct |
| 6 | Correct | 22 ms | 6604 KB | Output is correct |
| 7 | Correct | 22 ms | 6648 KB | Output is correct |
| 8 | Incorrect | 46 ms | 12776 KB | Output isn't correct |
| 9 | Halted | 0 ms | 0 KB | - |