This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Os parametros da função unlazy são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
void unlazy(int node, int tl, int tr){ | |
// Se não houver valor a ser propagado, não precisamos propagar | |
if(lz[node] == 0) return; | |
// Primeiro, atualizamos a árvore com o novo valor | |
tree[node] = lz[node]; | |
// Se houver filhos, propagamos o vaor para eles | |
if(tl != tr){ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Os parametros da função unlazy são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
void unlazy(int node, int tl, int tr){ | |
// Se não houver valor a ser propagado, não precisamos propagar | |
if(lz[node] == 0) return; | |
// Primeiro, atualizamos a árvore com o novo valor, somando ele vezes o número de vezes que aparecerá no intervalo | |
tree[node] = (tr-tl+1)*lz[node]; | |
// Se houver filhos, propagamos o vaor para eles, somando ao que já existe, pois pode ser que os filhos não | |
// tenham sido atualizados desde a última vez que essa função foi chamada em node |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Os parametros da função unlazy são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
void unlazy(int node, int tl, int tr){ | |
// Se não houver valor a ser propagado, não precisamos propagar | |
if(lz[node] == 0) return; | |
// Primeiro, atualizamos a árvore com o novo valor, somando ele vezes o número de vezes que aparecerá no intervalo | |
tree[node] = (tr-tl+1)*lz[node]; | |
// Se houver filhos, propagamos o vaor para eles, somando ao que já existe, pois pode ser que os filhos não | |
// tenham sido atualizados desde a última vez que essa função foi chamada em node |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
//como estamos lidando com número muito grandes, | |
//quase sempre trabalharemos com residuos modulares. | |
const ll MOD = 1e9 + 7; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Comentário NOIC - OBI Fase 3 P1 e P2 - Festa | |
// Complexidade: O(M*Saída) | |
// Escrito por Pedro Racchetti | |
#include<bits/stdc++.h> | |
using namespace std; | |
const int MAXM = 5e3 + 10; | |
typedef long long ll; | |
ll n, m; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Comentário NOIC - OBI Fase 3 P1 e P2 - Festa | |
// Complexidade: O(M) | |
// Escrito por Pedro Racchetti | |
#include<bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
// Como N e M podem ser bem grandes, usamos long long | |
ll n, m; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Comentário NOIC - OBI Fase 3 P1 e P2 - Festa | |
// Complexidade: O(M + Nlog N) | |
// Escrito por Pedro Racchetti | |
#include<bits/stdc++.h> | |
using namespace std; | |
#define esq(x) x << 1 | |
#define dir(x) (x<<1) | 1 | |
#define mid(x,y,t) ((x+y)>>1) + t |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Comentário NOIC - OBI Fase 3 P1 e P2 - Festa | |
// Complexidade: O(M + Nˆ2) | |
// Escrito por Pedro Racchetti | |
#include<bits/stdc++.h> | |
using namespace std; | |
const int MAXM = 15; | |
vector<int> fila; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Comentário NOIC - OBI Fase 3 PJ - Ogro | |
// Complexidade: O(N) | |
// Escrito por Pedro Racchetti | |
#include<bits/stdc++.h> | |
using namespace std; | |
int n; | |
int maoesq, maodir; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Os parametros da função unlazy são: | |
// O nó atual, tl e tr, o intervalo que o nó atual abrange, | |
void unlazy(int node, int tl, int tr){ | |
// Se não houver valor a ser propagado, não precisamos propagar | |
if(lz[node] == 0) return; | |
// Primeiro, atualizamos a árvore com o novo valor, somando ele vezes o número de vezes que aparecerá no intervalo | |
tree[node] = (tr-tl+1)*lz[node]; | |
// Se houver filhos, propagamos o vaor para eles, somando ao que já existe, pois pode ser que os filhos não | |
// tenham sido atualizados desde a última vez que essa função foi chamada em node |
NewerOlder