Submission #1266276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266276		_rain_	Progression (NOI20_progression)	C++20	59 / 100	174 ms	32128 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) 3e5;
	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';
		}
	}
}

namespace subtask2{
	bool check(){
		FOR(i , 1 , q) if (queri[i].t != 3) return false;
		return true;
	}
	
	class IT{
		public:
			vector<int> st;
			vector<int> lazy;
			
			void load_size(int n){
				st = lazy = vector<int> (n * 4 + 2 , 0);
				return;
			}
			
			void build(int id , int l , int r){
				if (l == r) st[id] = 0;
				else {
					int m = (l + r) / 2;
					build(id * 2 , l , m) , 
					build(id * 2 + 1 , m + 1 , r);
					st[id] = max(st[id * 2] , st[id * 2 + 1]);
				}
				return;
			}
			
				void refine(int id , int val){
					st[id] += val;
					lazy[id] += val;
					return;
				}
				
				void pushdown(int id){
					int & t = lazy[id];
						refine(id * 2 , t);
						refine(id * 2 + 1 , t);
					t = 0;
					return;
				}
			
			void update(int id , int l , int r , int u , int v , int val){
				if (l > v || r < u) return;
				if (u <= l && r <= v) {
					refine(id , val);
					return;
				}
				int m = (l + r) / 2;
				update(id * 2 , l , m , u , v , val);
				update(id * 2 + 1 , m + 1 , r , u , v , val);
				st[id] = max(st[id * 2] , st[id * 2 + 1]);
			}
			
			int Get(int id , int l , int r , int u , int v){
				if (l > v || r < u) return 0;
				if (u <= l && r <= v) return st[id];
				int m = (l + r) / 2;
				pushdown(id);
				return max(Get(id * 2 , l , m , u , v) , Get(id * 2 + 1 , m + 1 , r , u , v));
			}
	};
	
	IT st;
	vector<pair<int,int>> ask[N + 2];
	int ans[N + 2] = {};
	
	void main_code(){
		st.load_size(n);
		FOR(i , 1 , q) {
			if (queri[i].r - queri[i].l + 1 <= 2) ans[i] = queri[i].r - queri[i].l + 1;
			else {
				ask[queri[i].r].push_back({queri[i].l , i});
			}
		}
		for(int i = 2 ; i <= n; ++i){
			int last = i - 1;
			int ptr = i , t = a[i] - a[i - 1];
			while (ptr <= n && a[ptr] - a[ptr - 1] == t) ++ptr;
			
			for(int j = i - 1; j < ptr; ++j) {
				st.update(1 , 1 , n , i - 1 , j - 1 , 1);
				for(auto& x: ask[j]) ans[x.second] = st.Get(1 , 1 , n , x.first , j) + 1;
			}
			i = ptr - 1;
		}
		FOR(i , 1 , q) cout << ans[i] << '\n';
	}
}

namespace subtask3{
	bool check(){
		FOR(i , 1 , q){
//			cout << queri[i].l << ' ' << queri[i].r << '\n';
			if (queri[i].l == 1 && queri[i].r == n) continue;
			return false;
		}
		return true;
	}
	
	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(){
		int ans = calc(1 , n);
		FOR(i , 1 , q) {
			if (queri[i].t==3) cout << ans << '\n';
			else {
				if (queri[i].t == 2) ans = n;
			}
		}	
		return;
	}
}

namespace subtask4{
	bool check(){
		return true;
	}
	void main_code(){
		
	}
}

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;
		if (subtask2::check()) return subtask2::main_code() , 0;
		if (subtask3::check()) return subtask3::main_code() , 0;
	TIME_USED;
}

Compilation message (stderr)

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

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