제출 #1266384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266384		_rain_	Progression (NOI20_progression)	C++20	63 / 100	714 ms	216668 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1)<<(x))
#define TIME_USED cerr << endl << "TIME LAPSED : " << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	

const int N = (int) 1e6;
const LL inf = (LL) 1e18;
	int n , q;
	LL a[N + 2] = {};
	
	struct QUERY{
		int t;
		int l , r , s , c;
		
		void read(){
			cin >> t;
			if (t == 1 || t == 2) cin >> l >> r >> s >> c;
				else cin >> l >> r;
			return;
		}
	} queri[N + 2];
	
namespace subtask1{
	bool check(){
		return n <= 1e3 && q <= 1e3;
	}
	
	void patch(int l , int r , int s , int c){
		FOR(i , l , r) a[i] += (LL)s + (LL)(i - l) * c;
		return;
	}
	void rewrite(int l , int r , int s , int c){
		FOR(i , l , r) a[i] = (LL) s + (LL)(i - l) * c;
		return;
	}
	int calc(int l , int r){
		if (r - l + 1 <= 2) return r - l + 1;
		int ans = 2;
		for(int i = l + 1; i <= r; ++i){
			int t = a[i] - a[i - 1] , ptr = i;
			while (ptr <= r && a[ptr] - a[ptr - 1] == t) ++ptr;
			ans = max(ans , ptr - i + 1);
			i = ptr - 1;
		}
		return ans;
	}
	
	void main_code(){
		for(int i = 1; i <= q; ++i){
			if (queri[i].t == 1) patch(queri[i].l , queri[i].r , queri[i].s , queri[i].c);
			if (queri[i].t == 2) rewrite(queri[i].l , queri[i].r , queri[i].s , queri[i].c);
			if (queri[i].t == 3) cout << calc(queri[i].l , queri[i].r) << '\n';
		}
	}
}
	
	
		struct Node{
			int length;
			int prefix_length , suffix_length;
			int tot;
		
			LL prefix_value , suffix_value;
			LL max_value , min_value;
				
			Node(){
				length = suffix_length = prefix_length = 0;
				max_value = -inf , min_value = inf;
				prefix_value = 0 , suffix_value = 0;
				tot = 0;
				return;
			}
		};
		Node st[N * 4 + 2];
		
	Node operator + (Node a , Node b){
		Node c = Node();
			c.prefix_value = a.prefix_value , c.suffix_value = b.suffix_value;
			c.prefix_length = a.prefix_length , c.suffix_length = b.suffix_length;
			c.max_value = max(a.max_value , b.max_value) , 
			c.min_value = min(a.min_value , b.min_value);
			c.length = a.length + b.length;
			c.tot = max(a.tot , b.tot);
			
			bool same_a = false , same_b = false;
				same_a = (a.max_value == a.min_value);
				same_b = (b.min_value == b.max_value);	
			
			if (same_a && b.prefix_value == a.max_value) {
				c.prefix_length = a.length + b.prefix_length;
			}
			if (same_b && a.suffix_value == b.max_value){
				c.suffix_length = b.length + a.suffix_length;
			}
			
			if (a.suffix_value == b.prefix_value) maximize(c.tot , a.suffix_length + b.prefix_length);
			maximize(c.tot , max(c.prefix_length , c.suffix_length));
			
		return c;	
	}
	
	LL lst[N + 2] = {};
	LL lazy_1[N * 4 + 2] = {} , lazy_2[N * 4 + 2] = {};
	// 0 -> patch , 1 -> rewrite
	
		void build(int id , int l , int r){
			lazy_1[id] = 0; lazy_2[id] = -1;
			if (l == r) {
				st[id].tot = st[id].prefix_length = st[id].suffix_length = st[id].length = 1;
				st[id].max_value = st[id].min_value = lst[l];
				st[id].suffix_value = st[id].prefix_value = lst[l];
			}
			else{
				int m = (l + r) / 2;
				build(id * 2 , l , m) , 
				build(id * 2 + 1 , m + 1 , r);
				st[id] = st[id * 2] + st[id * 2 + 1];
			}
		}
		
			void refine(int id , LL val , int l , int r , int t){
				if (t == 0) {
					st[id].max_value += val , st[id].min_value += val;
					st[id].prefix_value += val , st[id].suffix_value += val;
					lazy_1[id] += val;
				}
				else{
					st[id].min_value = st[id].max_value = val;
					st[id].prefix_value = st[id].suffix_value = val;
					st[id].suffix_length = st[id].prefix_length = st[id].length = r - l + 1;
					st[id].tot = r - l + 1;
					lazy_2[id] = val;
				}
				return;
			}
			
			void pushdown(int id , int l , int r){
				LL &t1 = lazy_1[id] ;
				LL &t2 = lazy_2[id] ;
				
				int m = (l + r) / 2;
				if (t2 != -1){
					refine(id * 2 , t2 , l , m , 1);
					refine(id * 2 + 1 , t2 , m + 1 , r , 1);
					t2 = -1;
				}
				
				refine(id * 2 , t1 , l , m , 0);
				refine(id * 2 + 1 , t1 , m + 1 , r , 0);
				t1 = 0;
				
				return;
			}
		
		void update(int id , int l , int r , int u , int v , LL val , int t){
			if (l > v || r < u) return ;
			if (u <= l && r <= v){
				if (t == 1) refine(id , val , l , r , 1) , lazy_1[id] = 0;
				if (t == 0) refine(id , val , l , r , 0) ; // 1
				return;
			}
			int m = (l + r) / 2;
			pushdown(id , l , r);
			update(id * 2 , l , m , u , v , val , t);
			update(id * 2 + 1 , m + 1 , r , u , v , val , t);
			st[id] = st[id * 2] + st[id * 2 + 1];
		}
		
		Node Get(int id  , int l , int r , int u , int v){
			if (l > v || r < u) return Node();
			if (u <= l && r <= v) return st[id];
			int m = (l + r) / 2;
			pushdown(id , l , r);
			return Get(id * 2 , l , m , u , v) + Get(id * 2 + 1 , m + 1 , r , u , v);
		}
		
	LL ans(int l , int r){
		Node g = Get(1 , 1 , n  - 1 , l , r - 1);
		return g.tot + 1;
	}

	void patch(int l , int r , LL s , LL c){
		update(1 , 1 , n - 1 , l - 1 , l - 1 , +s , 0);
		update(1 , 1 , n - 1 , l  , r - 1 , c , 0);
		update(1 , 1 , n - 1 , r  , r  , -s - (LL)(r - l) * c , 0);
		return;
	}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> q;
		FOR(i , 1 , n) cin >> a[i];
		FOR(i,1,q) queri[i].read();
		if (subtask1::check()) return subtask1::main_code() , 0;
		FOR(i , 2 , n) lst[i - 1] = a[i] - a[i - 1];
		build(1 , 1 , n - 1);
		FOR(i,1,q){
			
			if (queri[i].t == 1) patch(queri[i].l , queri[i].r , queri[i].s , queri[i].c);
			if (queri[i].t == 3) cout << ans(queri[i].l , queri[i].r) << '\n';
		}
	TIME_USED;
}

컴파일 시 표준 에러 (stderr) 메시지

Progression.cpp: In function 'int main()':
Progression.cpp:219:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:220:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 0 / 11
• Subtask 5: 13 / 13
• Subtask 6: 0 / 17