Submission #166118

#	Time	Username	Problem	Language	Result	Execution time	Memory
166118		theStaticMind	Garaža (COCI17_garaza)	C++14	120 / 160	3841 ms	120848 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];
inline bool comp(ii& a,ii& b){
      return a.first>b.first||(a.first==b.first&&a.second>b.second);
}
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();
            vector<ii>ind;
            ind.pb({0,0});
            for(map<int,int>::iterator itr=L.suff.begin();itr!=L.suff.end();itr++){
                  ind.pb({itr->second,R.pre[itr->first]});
            }
            sort(all(ind),comp);
            int w=ind[0].second;
            for(int i=1;i<ind.size();i++){
                  cnt+=(long long int)((long long int)ind[i-1].first-(long long int)ind[i].first)*(long long int)w;
                  w=max(w,ind[i].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;
inline 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));
}
vector<node>t;
inline void query(int j,int a,int b,int x,int y){
      t[j]=node(0);
      if(y<a||b<x)return;
      if(a<=x&&y<=b)t[j]=seg[j];
      else{
            query(j*2,a,b,x,(x+y)/2),query(j*2+1,a,b,(x+y)/2+1,y);
            t[j].merge(t[j*2],t[j*2+1]);
            t[j*2]=node(0),t[j*2+1]=node(0);
      }
}
inline 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;
      scanf("%d %d",&n,&q);
      seg.resize(n,node(1));
      for(int i=0;i<n;i++){
            int x;
            scanf("%d",&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();
      t.resize(seg.size(),node(0));
      while(q--){
            int k,x,y;
            scanf("%d %d %d",&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--;
                  query(1,x,y,0,S-1);
                  printf("%d\n",t[1].cnt);
            }
      }
}

Compilation message (stderr)

garaza.cpp: In member function 'void node::merge(node&, node&)':
garaza.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=1;i<ind.size();i++){
                         ~^~~~~~~~~~~
garaza.cpp: In function 'void build()':
garaza.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=1;i<seg.size();i+=2){
                   ~^~~~~~~~~~~
garaza.cpp: In function 'int32_t main()':
garaza.cpp:144:41: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
                   printf("%d\n",t[1].cnt);
                                         ^
garaza.cpp:101:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d",&n,&q);
       ~~~~~^~~~~~~~~~~~~~~
garaza.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
             ~~~~~^~~~~~~~~
garaza.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d",&k,&x,&y);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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