Editorial for Cvjetici


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
var n,nn,i,x,y,c,d:longint;
    a:array[1..400000] of longint;
    b:array[1..100000,0..1] of longint;

function calc(node,l,r,x:longint):longint;
var mid,res:longint;
begin
     res:=0;
     if (l=x) and (r=x) then res:=a[node]
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then res:=calc(node shl 1,l,mid,x)+a[node]
          else res:=calc(node shl 1+1,mid+1,r,x)+a[node];
     end;
     calc:=res;
end;


procedure add(node,l,r,x,y:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then a[node]:=a[node]+1
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then add(node shl 1,l,mid,x,min(y,mid));
          if y>mid then add(node shl 1+1,mid+1,r,max(x,mid+1),y);
     end;
end;

procedure minus(node,l,r,x,val:longint);
var mid:longint;
begin
     if (l=x) and (r=x) then a[node]:=a[node]-val
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then minus(node shl 1,l,mid,x,val)
          else minus(node shl 1+1,mid+1,r,x,val);
     end;
end;

begin
     read(nn);
     n:=0;
     for i:=1 to nn do
     begin
          read(b[i,0],b[i,1]);
          n:=max(n,b[i,1]);
     end;
     for i:=1 to nn do
     begin
          x:=b[i,0]; y:=b[i,1];
          c:=calc(1,1,n,x);
          d:=calc(1,1,n,y);
          minus(1,1,n,x,c);
          minus(1,1,n,y,d);
          writeln(c+d);
          if x<y-1 then add(1,1,n,x+1,y-1);
     end;
end.

Code mẫu của happyboy99x

#include<iostream>
using namespace std;

const int N = 100000;
int bit[N];

void update(int idx, int v) {
    for(int x = idx; x < N; x |= x + 1)
        bit[x] += v;
}

void updateOne(int idx, int v) {
    bit[idx] += v;
    for(int z = idx | (idx + 1), x = idx + 1; x < N && x != z; x |= x + 1)
        bit[x] -= v;
}

int get(int idx) {
    int res = 0;
    for(int x = idx; x >= 0; x -= ~x & (x + 1))
        res += bit[x];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for(int i = 0; i < n; ++i) {
        int l, r; cin >> l >> r; --l; --r;
        int fl = get(l), fr = get(r);
        printf("%d\n", fl + fr);
        updateOne(l, -fl); updateOne(r, -fr);
        update(l + 1, 1); update(r, -1);
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int lim = 100005;
using namespace std;

int MAX[4 * lim], CNT[4 * lim], lazy[4 * lim];

struct node {
    int l, r, id;
    void diffuse() {
        if (lazy[id] == 0) return;
        MAX[id] += lazy[id];
        if (l != r) lazy[id << 1] = lazy[id << 1 | 1] += lazy[id];
        lazy[id] = 0;
    }
    node (int _l, int _r, int _id) {l = _l; r = _r; id = _id; diffuse();}
    node left() {return node(l, l + r >> 1, id << 1);}
    node right() {return node((l + r >> 1) + 1, r, id << 1 | 1);}
    void Assign(int i, int j) {
        if (l > r || r < i || j < l) return;
        if (i <= l && r <= j) {lazy[id]++; diffuse(); return;}
        left().Assign(i, j); right().Assign(i, j);
    }
    void Inc(int i) {
        if (l > r || r < i || i < l) return;
        if (l == r) {CNT[id] = MAX[id]; return;}
        left().Inc(i); right().Inc(i);
        CNT[id] = CNT[id << 1] + CNT[id << 1 | 1];
    }
};

int main() {
    int n, l, r;
    scanf("%d", &n);
    node Root (1, lim, 1);
    int last = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d %d", &l, &r);
        if (l + 1 < r)
            Root.Assign(l + 1, r - 1);
        Root.Inc(l); Root.Inc(r);
        printf("%d\n", CNT[1] - last);
        last = CNT[1];
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100011;
  snode=524288;
var
  f1,f2:text;
  ln,n:longint;
  l,r:array[1..MAXN] of longint;
  cover:array[1..snode] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
begin
  read(f1,n);
  for n:=1 to n do
    read(f1,l[n],r[n]);
  for n:=1 to n do
    ln:=max(ln,r[n]);
end;
procedure update(u,v,k:longint);
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if (v<l) or (r<u) then exit;
    if (u<=l) and (r<=v) then
      begin
        if k=1 then cover[i]+=1
        else cover[i]:=0;
        exit;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  visit(1,1,ln);
end;
function get(u:longint):longint;
var
  kq:longint;
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if l>r then exit;
    if (u<l) or (r<u) then exit;
    if (l=r) then
      begin
        kq:=cover[i];
        exit;
      end;
    if cover[i]>0 then
      begin
        cover[i<<1]+=cover[i];
        cover[i<<1+1]+=cover[i];
        cover[i]:=0;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  visit(1,1,ln);
  exit(kq);
end;
procedure solve;
var
  i,x,y:longint;
begin
  for i:=1 to n do
    begin
      x:=get(l[i]);
      y:=get(r[i]);
      writeln(f2,x+y);
      update(l[i]+1,r[i]-1,1);
      update(l[i],l[i],0);
      update(r[i],r[i],0);
    end;
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>

struct t_plant
{
       int left,right;
};

int plants;
t_plant plant[100100];
int minleft,maxright;

void enter()
{
     int p;
     scanf("%d",&plants);
     minleft = 200000; maxright = 0;
     for( p = 0;p<plants;p++)
     {
          scanf("%d %d",&plant[p].left,&plant[p].right);
          if(plant[p].left<minleft) minleft = plant[p].left;
          if(plant[p].right>maxright) maxright = plant[p].right;
     }
     maxright -= minleft;
     for(p = 0;p<plants;p++)
     {
           plant[p].left -= minleft;
           plant[p].right -= minleft;
     }
}

int norm,count[270000];

void init_counts()
{
     for(norm = 1;norm<=maxright;norm*=2);
}

int count_flowers(int pos)
{
    int p;
    int result = 0;
    for(p = norm+pos;p>0;p/=2) result+= count[p];
    count[norm+pos] -= result;
    return result;
}

void add_bar(int from,int to,int root,int width)
{
     if((from==0) &&(to == width-1)) count[root]++;
     else if(to<width/2) add_bar(from,to,2*root,width/2);
     else if(from>= width/2) add_bar(from-width/2,to-width/2,2*root+1,width/2);
     else
     {
         add_bar(from,width/2-1,2*root,width/2);
         add_bar(0,to-width/2,2*root+1,width/2);
     }
}

void grow_plants()
{
     int p,flowers;
     init_counts();
     for(p=0;p<plants;p++)
     {
         flowers = count_flowers(plant[p].left)+count_flowers(plant[p].right);
         printf("%d\n",flowers);
         if(plant[p].right> plant[p].left+1) add_bar(plant[p].left+1,plant[p].right-1,1,norm);
     }
}

int main()
{
    //freopen("CVJETICI.in","r",stdin);
    enter();
    grow_plants();
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program CVJETICI;
Const
  input  = '';
  output = '';
  maxn = 100000;
Var
  a: array[1..maxn] of integer;
  n: integer;

Procedure add(v,k: integer);
Begin
  While v <= maxn do
    Begin
      a[v]:= a[v] + k;
      v:= v + (v and -v);
    End;
End;

Function calc(v: integer): integer;
Var
  res: integer;
Begin
  res:= 0;
  While v > 0 do
    Begin
      res:= res + a[v];
      v:= v - (v and -v);
    End;
  calc:= res;
End;

Procedure solve;
Var
  fi,fo: text;
  i,u,v,x,y: integer;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);

  Readln(fi, n);
  For i:= 1 to n do
    Begin
      Readln(fi, u, v);

      x:= calc(u);
      y:= calc(v);
      Writeln(fo, x + y);

      add(u,-x);
      add(u + 1,x);

      add(v,-y);
      add(v + 1,y);

      add(u + 1,1);
      add(v,-1);
    End;

  Close(fo);
  Close(fi);
End;

Begin
  solve;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define fi   first
#define se   second
using namespace std;
typedef pair<int,int> ii;
int tree[MAX<<2];
ii a[MAX];
int n;
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) {
        scanf("%d",&a[i].fi);
        scanf("%d",&a[i].se);
    }
}
void pushdown(int i) {
    tree[2*i]+=tree[i];
    tree[2*i+1]+=tree[i];
    tree[i]=0;
}
void update(int i,int l,int r,int u,int v,int val) {
    if (l>v) return;
    if (r<u) return;
    if (l>r) return;
    if (v<u) return;
    if (u<=l && r<=v) {
        tree[i]+=val;
        return;
    }
    pushdown(i);
    int m=(l+r)/2;
    update(2*i,l,m,u,v,val);
    update(2*i+1,m+1,r,u,v,val);
}
int get(int u) {
    int i=1;
    int l=1;
    int r=100000;
    while (true) {
        if (l==r) {
            int tmp=tree[i];
            tree[i]=0;
            return (tmp);
        }
        pushdown(i);
        int m=(l+r)/2;
        if (m<u) {
            i=2*i+1;
            l=m+1;
        }
        else {
            i=2*i;
            r=m;
        }
    }
}
void process(void) {
    FOR(i,1,n) {
        printf("%d\n",get(a[i].fi)+get(a[i].se));
        update(1,1,100000,a[i].fi+1,a[i].se-1,1);
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}

var
    i, t, p, x, y, n : integer;
    b : array[1..110000] of integer;

procedure update(i, v : integer);
begin
    while i <= 110000 do
    begin
        inc(b[i], v);
        inc(i, i and (-i));
    end;
end;

function get(i : integer) : integer;
var
    r : integer;
begin
    r := 0;
    while i > 0 do
    begin
        inc(r, b[i]);
        dec(i, i and (-i));
    end;
    get := r;
end;

begin
    read(n);
    for i:=1 to n do
    begin
        read(x,y);
        t := get(x);
        p := get(y);
        writeln(t + p);
        update(x,-t);
        update(x+1,t);
        update(y,-p);
        update(y+1,p);
        if x + 1 < y then
        begin
            update(x+1,1);
            update(y,-1);
        end;
    end;
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.