oj.uz

답안 #673785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673785 2022-12-22T03:19:00 Z Baytoro 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 497 ms 188568 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
//#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e18,mod=998244353;
int n,m,k;
const int N=123456;
struct node{
	int sum,lazy,lx,rx,l,r;
	node(): sum(0),lazy(0),l(-1),r(-1) {}
} st[64*N];
int cnt=2;
void push(int x){
	int md=(st[x].rx+st[x].lx)/2;
	if(st[x].l==-1){
		st[x].l=cnt++;
		st[st[x].l].lx=st[x].lx;
		st[st[x].l].rx=md;
	}
	if(st[x].r==-1){
		st[x].r=cnt++;
		st[st[x].r].lx=md+1;
		st[st[x].r].rx=st[x].rx;
	}
	if(st[x].lazy){
		st[x].sum=st[x].rx-st[x].lx+1;
		st[st[x].l].lazy=st[st[x].r].lazy=1;
		st[x].lazy=0;
	}
}
void update(int x, int l, int r){
	push(x);
	if(l==st[x].lx && r==st[x].rx){
		st[x].lazy=1;
		push(x);
		return;
	}
	int md=(st[x].lx+st[x].rx)/2;
	if(l>md)
		update(st[x].r,l,r);
	else if(r<=md)
		update(st[x].l,l,r);
	else{
		update(st[x].l,l,md);
		update(st[x].r,md+1,r);
	}
	push(st[x].l);
	push(st[x].r);
	st[x].sum=st[st[x].l].sum+st[st[x].r].sum;
}
int query(int x, int l, int r){
	push(x);
	if(l==st[x].lx && r==st[x].rx)
		return st[x].sum;
	int md=(st[x].lx+st[x].rx)/2;
	if(l>md)
		return query(st[x].r,l,r);
	else if(r<=md)
		return query(st[x].l,l,r);
	else
		return query(st[x].l,l,md)+query(st[x].r,md+1,r);
}
void solve(){
	int m;
	cin>>m;
	int c=0;
	st[1].sum=0,st[1].lazy=0;
	st[1].lx=1,st[1].rx=2e9;
	for(int i=0;i<m;i++){
		int d, x, y;
		cin>>d>>x>>y;
		if(d==1){
			c=query(1,x+c,y+c);
			cout<<c<<endl;
		}
		else{
			update(1,x+c,y+c);
		}
	}
}
main(){
	//fopn("newbarn");
	//ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}
/*
3
2 1 1000000000
1 1 1000000000
1 1 1000000000
*/

Compilation message

apple.cpp:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int INF=1e18,mod=998244353;
      |               ^~~~
apple.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~
apple.cpp: In function 'void fopn(std::string)':
apple.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 185828 KB Output is correct
2 Correct 76 ms 185804 KB Output is correct
3 Correct 75 ms 185712 KB Output is correct
4 Correct 95 ms 185980 KB Output is correct
5 Correct 103 ms 185924 KB Output is correct
6 Correct 111 ms 186000 KB Output is correct
7 Correct 100 ms 185932 KB Output is correct
8 Correct 243 ms 186816 KB Output is correct
9 Correct 448 ms 187888 KB Output is correct
10 Correct 418 ms 187980 KB Output is correct
11 Correct 424 ms 187876 KB Output is correct
12 Correct 432 ms 187996 KB Output is correct
13 Correct 406 ms 188316 KB Output is correct
14 Correct 416 ms 188484 KB Output is correct
15 Correct 492 ms 188380 KB Output is correct
16 Correct 495 ms 188484 KB Output is correct
17 Correct 415 ms 188568 KB Output is correct
18 Correct 415 ms 188344 KB Output is correct
19 Correct 497 ms 188436 KB Output is correct
20 Correct 496 ms 188416 KB Output is correct