Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //A
- #include <bits/stdc++.h>
- using namespace std;
- void build(vector<pair<int, int>>& tree, int idx, int l, int r, vector<int>& a){
- if (r-l==1){
- tree[idx]={a[l], l};
- return;
- }
- int m=(l+r)/2;
- build(tree, 2*idx+1, l, m, a);
- build(tree, 2*idx+2, m, r, a);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- void change(vector<pair<int, int>>& tree, int l, int r, int idx, int i, int x){
- if (i<l || i>=r){
- return;
- }
- if (r-l==1){
- tree[idx]={x, i};
- return;
- }
- int m=(l+r)/2;
- change(tree, l, m, 2*idx+1, i, x);
- change(tree, m, r, 2*idx+2, i, x);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- pair<int, int> ans(vector<pair<int, int>>& tree, int idx, int l, int r, int L, int R){
- if (R<=l || L>=r){
- return {-1, -1};
- }
- if (l>=L && r<=R){
- return tree[idx];
- }
- int m=(l+r)/2;
- return max(ans(tree, 2*idx+1, l, m, L, R), ans(tree, 2*idx+2, m, r, L, R));
- }
- int main(){
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- int k;
- cin>>k;
- vector<pair<int, int>> tree(4*n);
- build(tree, 0, 0, n, a);
- while(k--){
- int l, r;
- cin>>l>>r;
- l--;
- cout<<ans(tree, 0, 0, n, l, r).first<<" "<<ans(tree, 0, 0, n, l, r).second+1<<"\n";
- }
- return 0;
- }
- //B
- #include <bits/stdc++.h>
- using namespace std;
- void build(vector<pair<int, int>>& tree, int idx, int l, int r, vector<int>& a){
- if (r-l==1){
- tree[idx]={a[l], l};
- return;
- }
- int m=(l+r)/2;
- build(tree, 2*idx+1, l, m, a);
- build(tree, 2*idx+2, m, r, a);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- void change(vector<pair<int, int>>& tree, int l, int r, int idx, int i, int x){
- if (i<l || i>=r){
- return;
- }
- if (r-l==1){
- tree[idx]={x, i};
- return;
- }
- int m=(l+r)/2;
- change(tree, l, m, 2*idx+1, i, x);
- change(tree, m, r, 2*idx+2, i, x);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- pair<int, int> ans(vector<pair<int, int>>& tree, int idx, int l, int r, int L, int R){
- if (R<=l || L>=r){
- return {-1, -1};
- }
- if (l>=L && r<=R){
- return tree[idx];
- }
- int m=(l+r)/2;
- return max(ans(tree, 2*idx+1, l, m, L, R), ans(tree, 2*idx+2, m, r, L, R));
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- int k;
- cin>>k;
- vector<pair<int, int>> tree(4*n);
- build(tree, 0, 0, n, a);
- while(k--){
- int l, r;
- cin>>l>>r;
- l--;
- cout<<ans(tree, 0, 0, n, l, r).second+1<<"\n";
- }
- return 0;
- }
- //C
- #include <bits/stdc++.h>
- using namespace std;
- struct Note{
- int pref;
- int suf;
- int ans;
- };
- void build(vector<Note>& tree, vector<int>& a, int v, int l, int r){
- if (r-l==1){
- if (a[l]==0){
- tree[v].pref=1;
- tree[v].suf=1;
- tree[v].ans=1;
- }else{
- tree[v].pref=0;
- tree[v].suf=0;
- tree[v].ans=0;
- }
- return;
- }
- int m=(l+r)/2;
- build(tree, a, 2*v+1, l, m);
- build(tree, a, 2*v+2, m, r);
- tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
- tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
- tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
- if (tree[2*v+2].ans==r-m){
- tree[v].suf=tree[2*v+1].suf+r-m;
- }else{
- tree[v].suf=tree[2*v+2].suf;
- }
- if (tree[2*v+1].ans==m-l) {
- tree[v].pref = m - l + tree[2 * v + 2].pref;
- }else{
- tree[v].pref=tree[2*v+1].pref;
- }
- }
- void change(vector<Note>& tree, vector<int>& a, int v, int l, int r, int pos, int x){
- if (r-l==1){
- if (x==0){
- tree[v].pref=1;
- tree[v].suf=1;
- tree[v].ans=1;
- }else{
- tree[v].pref=0;
- tree[v].suf=0;
- tree[v].ans=0;
- }
- return;
- }
- int m=(r+l)/2;
- if (pos<m){
- change(tree, a, 2*v+1, l, m, pos, x);
- }else{
- change(tree, a, 2*v+2, m,r, pos, x);
- }
- tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
- tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
- tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
- if (tree[2*v+2].ans==r-m){
- tree[v].suf=tree[2*v+1].suf+r-m;
- }else{
- tree[v].suf=tree[2*v+2].suf;
- }
- if (tree[2*v+1].ans==m-l) {
- tree[v].pref = m - l + tree[2 * v + 2].pref;
- }else{
- tree[v].pref=tree[2*v+1].pref;
- }
- }
- int ans(vector<Note>& tree, vector<int>& a, int v, int l, int r, int L, int R){
- if (L>=r || R<=l){
- return 0;
- }
- if (L<=l && R>=r){
- //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<tree[v].ans<<"\n";
- return tree[v].ans;
- }
- int m=(r+l)/2;
- if (L<m && R<m){
- return ans(tree, a, 2*v+1, l, m, L, R);
- }
- if (L>=m && R>=m){
- return ans(tree, a, 2*v+2, m, r, L, R);
- }
- //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref)<<"\n";
- int y=min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref);
- y=max(y, ans(tree, a, 2*v+1, l, m, L, R));
- y=max(y, ans(tree, a, 2*v+2, m, r, L, R));
- return y;
- }
- int main(){
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- vector<Note> tree(4*n);
- build(tree, a, 0, 0, n);
- int m;
- cin>>m;
- for (int j=0; j<m; j++){
- string s;
- cin>>s;
- if (s=="UPDATE"){
- int i, x;
- cin>>i>>x;
- i--;
- a[i]=x;
- change(tree, a, 0, 0, n, i, x);
- }else{
- int l, r;
- cin>>l>>r;
- l--;
- cout<<ans(tree, a, 0, 0, n, l, r)<<"\n";
- }
- }
- }
- //D
- #include <iostream>
- #include <vector>
- #include <string>
- #define int long long
- using namespace std;
- void build(vector<int>& tree, vector<int>& a, int v, int l, int r){
- if (r-l==1){
- tree[v]=a[l];
- return;
- }
- int m=(r+l)/2;
- build(tree, a, 2*v+1, l, m);
- build(tree, a, 2*v+2, m, r);
- tree[v]=tree[2*v+1]+tree[2*v+2];
- return;
- }
- void change(vector<int>& tree, vector<int>& a, int v, int l, int r, int pos, int x){
- if (r-l==1){
- tree[v] = x;
- return;
- }
- int m=(r+l)/2;
- if (pos<m){
- change(tree, a, 2*v+1, l, m, pos, x);
- }else{
- change(tree, a, 2*v+2, m, r, pos, x);
- }
- tree[v]=tree[2*v+1]+tree[2*v+2];
- return;
- }
- int sum(vector<int>& tree, vector<int>& a, int v, int l, int r, int L, int R){
- if (L>=r || R<=l){
- return 0;
- }
- if (L<=l && R>=r){
- return tree[v];
- }
- int m=(r+l)/2;
- int ans=sum(tree, a, 2*v+1, l, m, L, R)+sum(tree, a, 2*v+2, m, r, L, R);
- return ans;
- }
- signed main(){
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- if (a[i]==0){
- a[i]=1;
- }else{
- a[i]=0;
- }
- }
- vector<int> tree(4*n);
- build(tree, a, 0, 0, n);
- int m;
- cin>>m;
- for (int i=0; i<m; i++){
- char x;
- cin>>x;
- if (x=='u') {
- int p, q;
- cin >> p >> q;
- p--;
- if (q==0){
- a[p]=1;
- }else{
- a[p]=0;
- }
- change(tree, a, 0, 0, n, p, a[p]);
- }else{
- int p, q, k;
- cin>>p>>q>>k;
- p--;
- int l=p;
- int r=q+1;
- while(r-l>1){
- int m=(r+l)/2;
- if (sum(tree, a, 0, 0, n, p, m)<k){
- l=m;
- }else{
- r=m;
- }
- }
- if (r==q+1){
- cout<<"-1"<<"\n";
- }else{
- cout<<r<<"\n";
- }
- }
- }
- }
- //F
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- struct Note{
- int l;
- int r;
- int ans;
- int d=0;
- };
- void build(vector<Note>& tree, vector<int>& a, int L, int R, int i){
- tree[i].l=L;
- tree[i].r=R;
- if (R-L==1){
- tree[i].ans=a[L];
- return;
- }
- int M=(R+L)/2;
- build(tree, a, L, M, 2*i+1);
- build(tree, a, M, R, 2*i+2);
- tree[i].ans=max(tree[2*i+1].ans, tree[2*i+2].ans);
- }
- void push(vector<Note>& tree, int i){
- tree[2*i+1].d+=tree[i].d;
- tree[2*i+2].d+=tree[i].d;
- tree[i].d=0;
- }
- void change(vector<Note>& tree, int i, int x, int L, int R){
- if (tree[i].l>=R || tree[i].r<=L){
- return;
- }
- if(tree[i].l>=L && tree[i].r<=R){
- tree[i].d+=x;
- return;
- }
- push(tree, i);
- change(tree, 2*i+1, x, L, R);
- change(tree, 2*i+2, x, L, R);
- tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
- }
- int answer(vector<Note>& tree, int i, int L, int R){
- if (tree[i].l>=R || tree[i].r<=L){
- return -1;
- }
- if(tree[i].l>=L && tree[i].r<=R){
- return tree[i].ans+tree[i].d;
- }
- push(tree, i);
- int m1=answer(tree, 2*i+1, L, R);
- int m2=answer(tree, 2*i+2, L, R);
- tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
- return max(m1, m2);
- }
- signed main(){
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- vector<Note> tree(4*n);
- build(tree, a, 0, n, 0);
- int M;
- cin>>M;
- for (int i=0; i<M; i++){
- char x;
- cin>>x;
- if (x=='a'){
- int L, R, add;
- cin>>L>>R>>add;
- L--;
- change(tree, 0, add, L, R);
- }else{
- int i;
- cin>>i;
- i--;
- cout<<answer(tree, 0, i, i+1)<<"\n";
- }
- }
- return 0;
- }
- //H
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1000000;
- string a;
- struct Node {
- int open;
- int closed;
- };
- Node t[4*N];
- #define left 2 * v + 1
- #define right 2 * v + 2
- Node merge(Node l, Node r) {
- Node res;
- res.open = r.open;
- res.closed = l.closed;
- if (l.open >= r.closed) {
- res.open += l.open - r.closed;
- }
- else {
- res.closed += r.closed - l.open;
- }
- return res;
- }
- void build(int v, int l, int r) {
- if (r - l == 1) {
- if (a[l] == '(') {
- t[v] = Node { 1, 0 };
- }
- else {
- t[v] = Node{ 0,1 };
- }
- }
- else {
- int m = (r + l) / 2;
- build(left, l, m);
- build(right, m, r);
- t[v] = merge(t[left], t[right]);
- }
- }
- Node result(int v, int l, int r, int ql, int qr) {
- if (l >= ql && r <= qr) {
- return t[v];
- } else if (r <= ql || l >= qr) {
- return Node{0, 0};
- } else {
- int m = (r + l) / 2;
- Node p = result(left, l, m, ql, qr);
- Node q = result(right, m, r, ql, qr);
- return merge(p, q);
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> a;
- int k;
- cin >> k;
- int n = a.size();
- build(0, 0, n);
- for (int i = 0; i < k; ++i) {
- int l; int r;
- cin >> l >> r;
- l--;
- auto x = result(0, 0, n, l, r);
- cout << (r - l) - (x.open + x.closed) << '\n';
- }
- }
- //G
- #include <bits/stdc++.h>
- using namespace std;
- void build(vector<int>& tree, int idx, int l, int r, vector<int>& a){
- if (r-l==1){
- tree[idx]=a[l];
- return;
- }
- int m=(l+r)/2;
- build(tree, 2*idx+1, l, m, a);
- build(tree, 2*idx+2, m, r, a);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- void change(vector<int>& tree, int idx, int l, int r, int i, int x){
- if (l>i || r<=i){
- return;
- }
- if (r-l==1){
- tree[idx]=x;
- return;
- }
- int m=(l+r)/2;
- change(tree, 2*idx+1, l, m, i, x);
- change(tree, 2*idx+2, m, r, i, x);
- tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
- }
- int maximum(vector<int>& tree, int idx, int l, int r, int L, int R){
- if (l>=R || r<=L){
- return -1;
- }
- if (l>=L && r<=R){
- return tree[idx];
- }
- int m=(l+r)/2;
- return max(maximum(tree, 2*idx+1, l, m, L, R), maximum(tree, 2*idx+2, m, r, L, R));
- }
- int ans(vector<int>& tree, int idx, int l, int r, int L, int R, int x){
- if (r-l==1){
- if (l>=L && l<R && tree[idx]>=x){
- return l;
- }
- return -2;
- }
- int m=(l+r)/2;
- int t=-2;
- if (!(l>=R || r<=L)){
- if (tree[2*idx+1]>=x){
- t=ans(tree, 2*idx+1, l, m, L, R, x);
- }
- }
- if (t!=-2){
- return t;
- }
- return ans(tree, 2*idx+2, m, r, L, R, x);
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n, m;
- cin>>n>>m;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- vector<int> tree(4*n);
- build(tree, 0, 0, n, a);
- while(m--){
- int t, i, x;
- cin>>t>>i>>x;
- i--;
- if (t==0){
- change(tree, 0, 0, n, i, x);
- a[i]=x;
- }else{
- cout<<ans(tree, 0, 0, n, i, n, x)+1<<"\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement