API tools faq
paste
Advertisement
ekzolot

Untitled

ekzolot
May 4th, 2024
695
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.37 KB | None | 0 0
raw download clone embed print report
  1. //A
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. void build(vector<pair<int, int>>& tree, int idx, int l, int r, vector<int>& a){
  5.     if (r-l==1){
  6.         tree[idx]={a[l], l};
  7.         return;
  8.     }
  9.     int m=(l+r)/2;
  10.     build(tree, 2*idx+1, l, m, a);
  11.     build(tree, 2*idx+2, m, r, a);
  12.     tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
  13. }
  14. void change(vector<pair<int, int>>& tree, int l, int r, int idx, int i, int x){
  15.     if (i<l || i>=r){
  16.         return;
  17.     }
  18.     if (r-l==1){
  19.         tree[idx]={x, i};
  20.         return;
  21.     }
  22.     int m=(l+r)/2;
  23.     change(tree, l, m, 2*idx+1, i, x);
  24.     change(tree, m, r, 2*idx+2, i, x);
  25.     tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
  26. }
  27. pair<int, int> ans(vector<pair<int, int>>& tree, int idx, int l, int r, int L, int R){
  28.     if (R<=l || L>=r){
  29.         return {-1, -1};
  30.     }
  31.     if (l>=L && r<=R){
  32.         return tree[idx];
  33.     }
  34.     int m=(l+r)/2;
  35.     return max(ans(tree, 2*idx+1, l, m, L, R), ans(tree, 2*idx+2, m, r, L, R));
  36. }
  37. int main(){
  38.     int n;
  39.     cin>>n;
  40.     vector<int> a(n);
  41.     for (int i=0; i<n; i++){
  42.         cin>>a[i];
  43.     }
  44.     int k;
  45.     cin>>k;
  46.     vector<pair<int, int>> tree(4*n);
  47.     build(tree, 0, 0, n, a);
  48.     while(k--){
  49.         int l, r;
  50.         cin>>l>>r;
  51.         l--;
  52.         cout<<ans(tree, 0, 0, n, l, r).first<<" "<<ans(tree, 0, 0, n, l, r).second+1<<"\n";
  53.     }
  54.     return 0;
  55. }
  56.  
  57. //B
  58. #include <bits/stdc++.h>
  59. using namespace std;
  60. void build(vector<pair<int, int>>& tree, int idx, int l, int r, vector<int>& a){
  61.     if (r-l==1){
  62.         tree[idx]={a[l], l};
  63.         return;
  64.     }
  65.     int m=(l+r)/2;
  66.     build(tree, 2*idx+1, l, m, a);
  67.     build(tree, 2*idx+2, m, r, a);
  68.     tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
  69. }
  70. void change(vector<pair<int, int>>& tree, int l, int r, int idx, int i, int x){
  71.     if (i<l || i>=r){
  72.         return;
  73.     }
  74.     if (r-l==1){
  75.         tree[idx]={x, i};
  76.         return;
  77.     }
  78.     int m=(l+r)/2;
  79.     change(tree, l, m, 2*idx+1, i, x);
  80.     change(tree, m, r, 2*idx+2, i, x);
  81.     tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
  82. }
  83. pair<int, int> ans(vector<pair<int, int>>& tree, int idx, int l, int r, int L, int R){
  84.     if (R<=l || L>=r){
  85.         return {-1, -1};
  86.     }
  87.     if (l>=L && r<=R){
  88.         return tree[idx];
  89.     }
  90.     int m=(l+r)/2;
  91.     return max(ans(tree, 2*idx+1, l, m, L, R), ans(tree, 2*idx+2, m, r, L, R));
  92. }
  93. int main(){
  94.     ios::sync_with_stdio(0);
  95.     cin.tie(0);
  96.     cout.tie(0);
  97.     int n;
  98.     cin>>n;
  99.     vector<int> a(n);
  100.     for (int i=0; i<n; i++){
  101.         cin>>a[i];
  102.     }
  103.     int k;
  104.     cin>>k;
  105.     vector<pair<int, int>> tree(4*n);
  106.     build(tree, 0, 0, n, a);
  107.     while(k--){
  108.         int l, r;
  109.         cin>>l>>r;
  110.         l--;
  111.         cout<<ans(tree, 0, 0, n, l, r).second+1<<"\n";
  112.     }
  113.     return 0;
  114. }
  115.  
  116. //C
  117. #include <bits/stdc++.h>
  118. using namespace std;
  119. struct Note{
  120.     int pref;
  121.     int suf;
  122.     int ans;
  123. };
  124. void build(vector<Note>& tree, vector<int>& a, int v, int l, int r){
  125.     if (r-l==1){
  126.         if (a[l]==0){
  127.             tree[v].pref=1;
  128.             tree[v].suf=1;
  129.             tree[v].ans=1;
  130.         }else{
  131.             tree[v].pref=0;
  132.             tree[v].suf=0;
  133.             tree[v].ans=0;
  134.         }
  135.         return;
  136.     }
  137.     int m=(l+r)/2;
  138.     build(tree, a, 2*v+1, l, m);
  139.     build(tree, a, 2*v+2, m, r);
  140.     tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
  141.     tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
  142.     tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
  143.     if (tree[2*v+2].ans==r-m){
  144.         tree[v].suf=tree[2*v+1].suf+r-m;
  145.     }else{
  146.         tree[v].suf=tree[2*v+2].suf;
  147.     }
  148.     if (tree[2*v+1].ans==m-l) {
  149.         tree[v].pref = m - l + tree[2 * v + 2].pref;
  150.     }else{
  151.         tree[v].pref=tree[2*v+1].pref;
  152.     }
  153. }
  154. void change(vector<Note>& tree, vector<int>& a, int v, int l, int r, int pos, int x){
  155.     if (r-l==1){
  156.         if (x==0){
  157.             tree[v].pref=1;
  158.             tree[v].suf=1;
  159.             tree[v].ans=1;
  160.         }else{
  161.             tree[v].pref=0;
  162.             tree[v].suf=0;
  163.             tree[v].ans=0;
  164.         }
  165.         return;
  166.     }
  167.     int m=(r+l)/2;
  168.     if (pos<m){
  169.         change(tree, a, 2*v+1, l, m, pos, x);
  170.     }else{
  171.         change(tree, a, 2*v+2, m,r, pos, x);
  172.     }
  173.     tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
  174.     tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
  175.     tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
  176.     if (tree[2*v+2].ans==r-m){
  177.         tree[v].suf=tree[2*v+1].suf+r-m;
  178.     }else{
  179.         tree[v].suf=tree[2*v+2].suf;
  180.     }
  181.     if (tree[2*v+1].ans==m-l) {
  182.         tree[v].pref = m - l + tree[2 * v + 2].pref;
  183.     }else{
  184.         tree[v].pref=tree[2*v+1].pref;
  185.     }
  186. }
  187. int ans(vector<Note>& tree, vector<int>& a, int v, int l, int r, int L, int R){
  188.     if (L>=r || R<=l){
  189.         return 0;
  190.     }
  191.     if (L<=l && R>=r){
  192.         //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<tree[v].ans<<"\n";
  193.         return tree[v].ans;
  194.     }
  195.     int m=(r+l)/2;
  196.     if (L<m && R<m){
  197.         return ans(tree, a, 2*v+1, l, m, L, R);
  198.     }
  199.     if (L>=m && R>=m){
  200.         return ans(tree, a, 2*v+2, m, r, L, R);
  201.     }
  202.     //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref)<<"\n";
  203.     int y=min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref);
  204.     y=max(y, ans(tree, a, 2*v+1, l, m, L, R));
  205.     y=max(y, ans(tree, a, 2*v+2, m, r, L, R));
  206.     return y;
  207. }
  208. int main(){
  209.     int n;
  210.     cin>>n;
  211.     vector<int> a(n);
  212.     for (int i=0; i<n; i++){
  213.         cin>>a[i];
  214.     }
  215.     vector<Note> tree(4*n);
  216.     build(tree, a, 0, 0, n);
  217.     int m;
  218.     cin>>m;
  219.     for (int j=0; j<m; j++){
  220.         string s;
  221.         cin>>s;
  222.         if (s=="UPDATE"){
  223.             int i, x;
  224.             cin>>i>>x;
  225.             i--;
  226.             a[i]=x;
  227.             change(tree, a, 0, 0, n, i, x);
  228.         }else{
  229.             int l, r;
  230.             cin>>l>>r;
  231.             l--;
  232.             cout<<ans(tree, a, 0, 0, n, l, r)<<"\n";
  233.         }
  234.     }
  235. }
  236.  
  237. //D
  238. #include <iostream>
  239. #include <vector>
  240. #include <string>
  241. #define int long long
  242. using namespace std;
  243. void build(vector<int>& tree, vector<int>& a, int v, int l, int r){
  244.     if (r-l==1){
  245.         tree[v]=a[l];
  246.         return;
  247.     }
  248.     int m=(r+l)/2;
  249.     build(tree, a, 2*v+1, l, m);
  250.     build(tree, a, 2*v+2, m, r);
  251.     tree[v]=tree[2*v+1]+tree[2*v+2];
  252.     return;
  253. }
  254. void change(vector<int>& tree, vector<int>&  a, int v, int l, int r, int pos, int x){
  255.     if (r-l==1){
  256.         tree[v] = x;
  257.         return;
  258.     }
  259.     int m=(r+l)/2;
  260.     if (pos<m){
  261.         change(tree, a, 2*v+1, l, m, pos, x);
  262.     }else{
  263.         change(tree, a, 2*v+2, m, r, pos, x);
  264.     }
  265.     tree[v]=tree[2*v+1]+tree[2*v+2];
  266.     return;
  267. }
  268. int sum(vector<int>& tree, vector<int>& a, int v, int l, int r, int L, int R){
  269.     if (L>=r || R<=l){
  270.         return 0;
  271.     }
  272.     if (L<=l && R>=r){
  273.         return tree[v];
  274.     }
  275.     int m=(r+l)/2;
  276.     int ans=sum(tree, a, 2*v+1, l, m, L, R)+sum(tree, a, 2*v+2, m, r, L, R);
  277.     return ans;
  278. }
  279. signed main(){
  280.     ios::sync_with_stdio(false);
  281.     cin.tie(nullptr);
  282.     cout.tie(nullptr);
  283.     int n;
  284.     cin>>n;
  285.     vector<int> a(n);
  286.     for (int i=0; i<n; i++){
  287.         cin>>a[i];
  288.         if (a[i]==0){
  289.             a[i]=1;
  290.         }else{
  291.             a[i]=0;
  292.         }
  293.     }
  294.     vector<int> tree(4*n);
  295.     build(tree, a, 0, 0, n);
  296.     int m;
  297.     cin>>m;
  298.     for (int i=0; i<m; i++){
  299.         char x;
  300.         cin>>x;
  301.         if (x=='u') {
  302.             int p, q;
  303.             cin >> p >> q;
  304.             p--;
  305.             if (q==0){
  306.                 a[p]=1;
  307.             }else{
  308.                 a[p]=0;
  309.             }
  310.             change(tree, a, 0, 0, n, p, a[p]);
  311.         }else{
  312.             int p, q, k;
  313.             cin>>p>>q>>k;
  314.             p--;
  315.             int l=p;
  316.             int r=q+1;
  317.             while(r-l>1){
  318.                 int m=(r+l)/2;
  319.                 if (sum(tree, a, 0, 0, n, p, m)<k){
  320.                     l=m;
  321.                 }else{
  322.                     r=m;
  323.                 }
  324.             }
  325.             if (r==q+1){
  326.                 cout<<"-1"<<"\n";
  327.             }else{
  328.                 cout<<r<<"\n";
  329.             }
  330.         }
  331.     }
  332. }
  333.  
  334.  
  335. //F
  336. #include <bits/stdc++.h>
  337. #define int long long
  338. using namespace std;
  339. struct Note{
  340.     int l;
  341.     int r;
  342.     int ans;
  343.     int d=0;
  344. };
  345. void build(vector<Note>& tree, vector<int>& a, int L, int R, int i){
  346.     tree[i].l=L;
  347.     tree[i].r=R;
  348.     if (R-L==1){
  349.         tree[i].ans=a[L];
  350.         return;
  351.     }
  352.     int M=(R+L)/2;
  353.     build(tree, a, L, M, 2*i+1);
  354.     build(tree, a, M, R, 2*i+2);
  355.     tree[i].ans=max(tree[2*i+1].ans, tree[2*i+2].ans);
  356. }
  357. void push(vector<Note>& tree, int i){
  358.     tree[2*i+1].d+=tree[i].d;
  359.     tree[2*i+2].d+=tree[i].d;
  360.     tree[i].d=0;
  361. }
  362. void change(vector<Note>& tree, int i, int x, int L, int R){
  363.     if (tree[i].l>=R || tree[i].r<=L){
  364.         return;
  365.     }
  366.     if(tree[i].l>=L && tree[i].r<=R){
  367.         tree[i].d+=x;
  368.         return;
  369.     }
  370.     push(tree, i);
  371.     change(tree, 2*i+1, x, L, R);
  372.     change(tree, 2*i+2, x, L, R);
  373.     tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
  374. }
  375. int answer(vector<Note>& tree, int i, int L, int R){
  376.     if (tree[i].l>=R || tree[i].r<=L){
  377.         return -1;
  378.     }
  379.     if(tree[i].l>=L && tree[i].r<=R){
  380.         return tree[i].ans+tree[i].d;
  381.     }
  382.     push(tree, i);
  383.     int m1=answer(tree, 2*i+1, L, R);
  384.     int m2=answer(tree, 2*i+2, L, R);
  385.     tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
  386.     return max(m1, m2);
  387. }
  388. signed main(){
  389.     int n;
  390.     cin>>n;
  391.     vector<int> a(n);
  392.     for (int i=0; i<n; i++){
  393.         cin>>a[i];
  394.     }
  395.     vector<Note> tree(4*n);
  396.     build(tree, a, 0, n, 0);
  397.     int M;
  398.     cin>>M;
  399.     for (int i=0; i<M; i++){
  400.         char x;
  401.         cin>>x;
  402.         if (x=='a'){
  403.             int L, R, add;
  404.             cin>>L>>R>>add;
  405.             L--;
  406.             change(tree, 0, add, L, R);
  407.         }else{
  408.             int i;
  409.             cin>>i;
  410.             i--;
  411.             cout<<answer(tree, 0, i, i+1)<<"\n";
  412.         }
  413.     }
  414.     return 0;
  415. }
  416.  
  417. //H
  418. #include <bits/stdc++.h>
  419. using namespace std;
  420. const int N = 1000000;
  421. string a;
  422. struct Node {
  423.     int open;
  424.     int closed;
  425. };
  426. Node t[4*N];
  427. #define left  2 * v + 1
  428. #define right  2 * v + 2
  429. Node merge(Node l, Node r) {
  430.     Node res;
  431.     res.open = r.open;
  432.     res.closed = l.closed;
  433.     if (l.open >= r.closed) {
  434.         res.open += l.open - r.closed;
  435.     }
  436.     else {
  437.         res.closed += r.closed - l.open;
  438.     }
  439.     return res;
  440. }
  441. void build(int v, int l, int r) {
  442.     if (r - l == 1) {
  443.         if (a[l] == '(') {
  444.             t[v] = Node { 1, 0 };
  445.         }
  446.         else {
  447.             t[v] =  Node{ 0,1 };
  448.         }
  449.     }
  450.     else {
  451.         int m = (r + l) / 2;
  452.         build(left, l, m);
  453.         build(right, m, r);
  454.         t[v] = merge(t[left], t[right]);
  455.     }
  456. }
  457.  
  458. Node result(int v, int l, int r, int ql, int qr) {
  459.     if (l >= ql && r <= qr) {
  460.         return t[v];
  461.     } else if (r <= ql || l >= qr) {
  462.         return Node{0, 0};
  463.     } else {
  464.         int m = (r + l) / 2;
  465.         Node p = result(left, l, m, ql, qr);
  466.         Node q = result(right, m, r, ql, qr);
  467.         return merge(p, q);
  468.  
  469.     }
  470. }
  471. int main() {
  472.     ios_base::sync_with_stdio(0);
  473.     cin.tie(0);
  474.     cin >> a;
  475.     int k;
  476.     cin >> k;
  477.     int n = a.size();
  478.     build(0, 0, n);
  479.     for (int i = 0; i < k; ++i) {
  480.         int l; int r;
  481.         cin >> l >> r;
  482.         l--;
  483.         auto x = result(0, 0, n, l, r);
  484.         cout << (r - l) - (x.open + x.closed) << '\n';
  485.     }
  486. }
  487.  
  488.  
  489. //G
  490. #include <bits/stdc++.h>
  491. using namespace std;
  492. void build(vector<int>& tree, int idx, int l, int r, vector<int>& a){
  493.     if (r-l==1){
  494.         tree[idx]=a[l];
  495.         return;
  496.     }
  497.     int m=(l+r)/2;
  498.     build(tree, 2*idx+1, l, m, a);
  499.     build(tree, 2*idx+2, m, r, a);
  500.     tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
  501. }
  502. void change(vector<int>& tree, int idx, int l, int r, int i, int x){
  503.     if (l>i || r<=i){
  504.         return;
  505.     }
  506.     if (r-l==1){
  507.         tree[idx]=x;
  508.         return;
  509.     }
  510.     int m=(l+r)/2;
  511.     change(tree, 2*idx+1, l, m, i, x);
  512.     change(tree, 2*idx+2, m, r, i, x);
  513.     tree[idx]=max(tree[2*idx+1], tree[2*idx+2]);
  514. }
  515. int maximum(vector<int>& tree, int idx, int l, int r, int L, int R){
  516.     if (l>=R || r<=L){
  517.         return -1;
  518.     }
  519.     if (l>=L && r<=R){
  520.         return tree[idx];
  521.     }
  522.     int m=(l+r)/2;
  523.     return max(maximum(tree, 2*idx+1, l, m, L, R), maximum(tree, 2*idx+2, m, r, L, R));
  524. }
  525. int ans(vector<int>& tree, int idx, int l, int r, int L, int R, int x){
  526.     if (r-l==1){
  527.         if (l>=L && l<R && tree[idx]>=x){
  528.             return l;
  529.         }
  530.         return -2;
  531.     }
  532.     int m=(l+r)/2;
  533.     int t=-2;
  534.     if (!(l>=R || r<=L)){
  535.         if (tree[2*idx+1]>=x){
  536.             t=ans(tree, 2*idx+1, l, m, L, R, x);
  537.         }
  538.     }
  539.     if (t!=-2){
  540.         return t;
  541.     }
  542.     return ans(tree, 2*idx+2, m, r, L, R, x);
  543. }
  544. int main(){
  545.     ios::sync_with_stdio(0);
  546.     cin.tie(0);
  547.     cout.tie(0);
  548.     int n, m;
  549.     cin>>n>>m;
  550.     vector<int> a(n);
  551.     for (int i=0; i<n; i++){
  552.         cin>>a[i];
  553.     }
  554.     vector<int> tree(4*n);
  555.     build(tree, 0, 0, n, a);
  556.     while(m--){
  557.         int t, i, x;
  558.         cin>>t>>i>>x;
  559.         i--;
  560.         if (t==0){
  561.             change(tree, 0, 0, n, i, x);
  562.             a[i]=x;
  563.         }else{
  564.             cout<<ans(tree, 0, 0, n, i, n, x)+1<<"\n";
  565.         }
  566.     }
  567. }
  568.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!