Cod sursa(job #3227682)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 2 mai 2024 14:26:01
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <vector>
#include <bitset>
#include <stack>
#include <list>
#include <iterator>
#include <complex>
#include <string>
#include <tuple>
#include <array>
#include <valarray>
#include <regex> 
#include <random>
#include <cassert>
using namespace std;
#ifdef ONPC
void read(int& num) {
	cin >> num;
}
void write(unsigned int x) {
	cout << x << "\n";
}
#else
__attribute__((always_inline)) void read(int& num) {
	static char inBuffer[0x30D40];
	static unsigned int p = 0x30D3F; num = 0x0;
	while (inBuffer[p] < 0x30 | inBuffer[p] > 0x39) {
		++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
	}
	while (inBuffer[p] > 0x2F & inBuffer[p] < 0x3A) {
		num = num * 0xA + inBuffer[p] - 0x30;
		++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
	}
}
char outBuffer[0x61A80]; unsigned int p;
__attribute__((always_inline)) void write(unsigned int x) {
	unsigned int digits = x > 0x3B9AC9FF ? 0xA :
		x > 0x5F5E0FF ? 0x9 :
		x > 0x98967F ? 0x8 :
		x > 0xF423F ? 0x7 :
		x > 0x1869F ? 0x6 :
		x > 0x270F ? 0x5 :
		x > 0x3E7 ? 0x4 :
		x > 0x63 ? 0x3 :
		x > 0x9 ? 0x2 : 0x1;
	for (unsigned int i = ~- digits; ~i; --i) {
		outBuffer[p + i] = x % 0xA + 0x30;
		x = x / 0xA;
	}
	p = p + digits; outBuffer[p++] = 0x0a;
}
#endif
int main() {
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	freopen("kami.in", "r", stdin);
	freopen("kami.out", "w", stdout);
#endif
	int n;
	read(n);
	vector<int64_t> a(n + 1);
	a[0] = (int64_t)(1e18);
	for (int i = 1; i <= n; i++) {
		int x;
		read(x);
		a[i] = x;
	}
	int tt;
	read(tt);
	while (tt--) {
		int tp, i;
		read(tp);
		read(i);
		assert(tp == 0 || tp == 1);
		assert(1 <= i && i <= n);
		if (tp == 0) {
			int x;
			read(x);
			a[i] = x;
			continue;
		}
		assert(tp == 1);
		int j = i;
		int64_t sum = a[i];
		while (a[j - 1] < sum) {
			j--;
			sum += a[j];
		}
		//cout << j - 1 << "\n";
		write(j - 1);
	}
#ifndef ONPC
	puts(outBuffer);
#endif
	return 0;
}