Submission #166110

#	Time	Username	Problem	Language	Result	Execution time	Memory
166110		theStaticMind	Garaža (COCI17_garaza)	C++14	120 / 160	4024 ms	164044 KiB

garaza

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
vector<int>arr;
map<int,int>F[100005];
struct node{
      long long int cnt;
      int size;
      map<int,int>pre,suff;
      node(int s){
            cnt=0;
            size=s;
      }
      void merge(node L,node R){
            size=L.size+R.size;
            if(L.size==0){
                  cnt=R.cnt;
                  pre=R.pre;
                  suff=R.suff;
                  return;
            }
            if(R.size==0){
                  cnt=L.cnt;
                  pre=L.pre;
                  suff=L.suff;
                  return;
            }
            pre.clear();
            suff.clear();
            map<int,int>ind;
            ind[0]=0;
            for(map<int,int>::iterator itr=L.suff.begin();itr!=L.suff.end();itr++){
                  ind[itr->second]=max(ind[itr->second],R.pre[itr->first]);
            }
            int p=ind.rbegin()->first;
            int w=ind.rbegin()->second;
            for(map<int,int>::reverse_iterator itr=(++ind.rbegin());itr!=ind.rend();itr++){
                  cnt+=(long long int)((long long int)p-(long long int)itr->first)*(long long int)w;
                  p=itr->first;
                  w=max(w,itr->second);
            }
            cnt+=L.cnt+R.cnt;
            pre=L.pre;
            for(map<int,int>::iterator itr=L.pre.begin();itr!=L.pre.end();itr++){
                  if(itr->second==L.size)pre[itr->first]=itr->second+R.pre[itr->first];
            }
            suff=R.suff;
            for(map<int,int>::iterator itr=R.suff.begin();itr!=R.suff.end();itr++){
                  if(itr->second==R.size)suff[itr->first]=itr->second+L.suff[itr->first];
            }
      }
};
vector<node>seg;
int S;
void build(){
      S=(1<<(int)ceil(log2(seg.size())));
      int l=S-seg.size();
      for(int i=0;i<l;i++)seg.pb(node(0));
      reverse(all(seg));
      for(int i=1;i<seg.size();i+=2){
            node temp(0);
            temp.merge(seg[i],seg[i-1]);
            seg.pb(temp);
      }
      seg.pb(node(0));
      reverse(all(seg));
}
node query(int j,int a,int b,int x,int y){
      node temp(0);
      if(y<a||b<x)return temp;
      if(a<=x&&y<=b)return seg[j];
      temp.merge(query(j*2,a,b,x,(x+y)/2),query(j*2+1,a,b,(x+y)/2+1,y));
      return temp;
}
void update(int j){
      while(j>0){
            seg[j]=node(0);
            seg[j].merge(seg[j*2],seg[j*2+1]);
            j/=2;
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
 //     freopen("q.gir","r",stdin);
 //     freopen("q.cik","w",stdout);
      int n,q;
      cin>>n>>q;
      seg.resize(n,node(1));
      for(int i=0;i<n;i++){
            int x;
            cin>>x;
            arr.pb(x);
            for(int j=2;j*j<=x;j++){
                  if(x%j==0){
                        F[i][j]=1;
                        while(x%j==0)x/=j;
                  }
            }
            if(x>1)F[i][x]=1;
            seg[i].pre=F[i];
            seg[i].suff=F[i];
            if(F[i].empty())seg[i].cnt=0;
            else seg[i].cnt=1;
      }
      build();
      while(q--){
            int k,x,y;
            cin>>k>>x>>y;
            if(k==1){
                  x--;
                  F[x].clear();
                  for(int j=2;j*j<=y;j++){
                        if(y%j==0){
                              F[x][j]=1;
                              while(y%j==0)y/=j;
                        }
                  }
                  if(y>1)F[x][y]=1;
                  int i=seg.size()-S+x;
                  seg[i].pre=F[x];
                  seg[i].suff=F[x];
                  if(F[x].empty())seg[i].cnt=0;
                  else seg[i].cnt=1;
                  update(i/2);
            }
            else{
                  x--,y--;
                  cout<<query(1,x,y,0,S-1).cnt<<"\n";
            }
      }
}

Compilation message (stderr)

garaza.cpp: In function 'void build()':
garaza.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=1;i<seg.size();i+=2){
                   ~^~~~~~~~~~~

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40
• Subtask 4: 0 / 40