Submission #617440

#	Time	Username	Problem	Language	Result	Execution time	Memory
617440		patrikpavic2	Fish 2 (JOI22_fish2)	C++17	100 / 100	1504 ms	43280 KiB

fish2

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define W Y.X
#define Z Y.Y
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < ll, ll > pll;
typedef pair < ll, pll > str;
typedef vector < str > vstr;

const int N = 1e5 + 500;
const int OFF = (1 << 17);

vstr Tl[2 * OFF], Tr[2 * OFF];
int A[N], n;

void print(vstr &v){
	for(str &tmp : v) printf(" (%lld %lld %lld), ", tmp.X, tmp.W, tmp.Z);
	printf("\n");
}

void mrg(vstr &Al, vstr &Ar, vstr &Bl, vstr &C){
	if((int)Al.size() == 0) {C = Bl; return; }
	if((int)Bl.size() == 0) {C = Al; return; }
	//printf("Al : "); print(Al);
	//printf("Ar : "); print(Ar);
	//printf("Bl : "); print(Bl);
	C.clear();
	int gd = 0, uzA = 1, uzB = 0;
	ll cur = Ar[0].X;
	for(;1;){ // popravljam Al
		bool nes = 0;
		while(uzA < (int)Ar.size() && cur >= Ar[uzA].Z)
			cur += Ar[uzA].X - Ar[uzA - 1].X, uzA++, nes = 1;
		while(uzB < (int)Bl.size() && cur >= Bl[uzB].Z)
			cur += Bl[uzB].X - (uzB ? Bl[uzB - 1].X : 0), uzB++, nes = 1;
		if(uzA == (int)Ar.size())
			break;
		else if(!nes){
			cur += Ar[uzA].X - Ar[uzA - 1].X;
			gd = uzA++;
		}
	}
	int gd2 = 0; uzA = 0, uzB = 1;
	cur = Bl[0].X;
	for(;1;){ // barem tolko s Br kraja
		bool nes = 0;
		while(uzA < (int)Ar.size() && cur >= Ar[uzA].Z)
			cur += Ar[uzA].X - (uzA ? Ar[uzA - 1].X : 0), uzA++, nes = 1;
		while(uzB < (int)Bl.size() && cur >= Bl[uzB].Z)
			cur += Bl[uzB].X - Bl[uzB - 1].X, uzB++, nes = 1;
		if(uzA == (int)Ar.size())
			break;
		else if(!nes){
			if(uzB == (int)Bl.size()){
				gd2 = N; break;
			}
			cur += Bl[uzB].X - Bl[uzB - 1].X;
			gd2 = uzB++;
		}
	}
	int jos = 0;
	for(int i = gd;i + 1 < (int)Ar.size();i++)
		jos += Ar[i].W;
	for(int i = 0;i + 1 < (int)Al.size();i++)
		C.PB(Al[i]);
	cur = Al.back().X; ll trb = Al.back().Z;
	int kl = Al.back().W + jos;
	int dod = 0;
	for(;;){
		while(dod < (int)Bl.size() && cur >= Bl[dod].Z){
			cur += Bl[dod].X - (dod ? Bl[dod - 1].X : 0);
			if(dod >= gd2) 
				kl += Bl[dod].W;
			dod++;
		}
		C.PB({cur, {kl, trb}});
		if(dod == (int)Bl.size()) break;
		kl = (Bl[dod].X >= Al.back().Z ? Bl[dod].W : 0); trb = Bl[dod].Z;
		cur += Bl[dod].X - (dod ? Bl[dod - 1].X : 0);
		dod++; 	
	}
}

void update(int i, int x){
	A[i] = x;
	Tl[OFF + i] = {{A[i], {1, A[i]}}}; Tr[OFF + i] = Tl[OFF + i];
	for(i = (i + OFF) / 2 ; i ; i /= 2){
		mrg(Tl[2 * i], Tr[2 * i], Tl[2 * i + 1], Tl[i]);
		//print(Tl[i]);
		mrg(Tr[2 * i + 1], Tl[2 * i + 1], Tr[2 * i], Tr[i]);
		//print(Tr[i]);
	} 
}

vstr Ql, QQl;

void query(int i, int a, int b, int lo, int hi){
	if(lo <= a && b <= hi){
		mrg(Tl[i], Tr[i], Ql, QQl); 
		Ql = QQl; return;
	}
	if(a > hi || b < lo) return;
	query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
	query(2 * i, a, (a + b) / 2, lo, hi);
}

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		Tl[OFF + i] = {{A[i], {1, A[i]}}}; Tr[OFF + i] = Tl[OFF + i];		
	}
	for(int i = OFF - 1 ; i ; i--){
	//	printf("spajam u %d\n", i);
		//printf("T[ %d ] : \n", i);
		mrg(Tl[2 * i], Tr[2 * i], Tl[2 * i + 1], Tl[i]);
		//print(Tl[i]);
		mrg(Tr[2 * i + 1], Tl[2 * i + 1], Tr[2 * i], Tr[i]);
		//print(Tr[i]);
	}
	int q; scanf("%d", &q);
	for(;q--;){
		int ty; scanf("%d", &ty);
		if(ty == 1){
			int pos, x; scanf("%d%d", &pos, &x);
			update(pos - 1, x);
		}
		else{
			int l, r; scanf("%d%d", &l, &r); l--, r--;
			Ql.clear(); QQl.clear();
			query(1, 0, OFF - 1, l, r);
			printf("%d\n", Ql.back().W);
		}
	}
	return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'int main()':
fish2.cpp:141:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  141 |    printf("%d\n", Ql.back().W);
      |            ~^
      |             |
      |             int
      |            %lld
fish2.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
fish2.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
fish2.cpp:132:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
fish2.cpp:134:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |    int pos, x; scanf("%d%d", &pos, &x);
      |                ~~~~~^~~~~~~~~~~~~~~~~~
fish2.cpp:138:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |    int l, r; scanf("%d%d", &l, &r); l--, r--;
      |              ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17