제출 #307989

#제출 시각아이디문제언어결과실행 시간메모리
307989AngelKnowsRectangles (IOI19_rect)C++14
0 / 100
2068 ms758640 KiB
#include "rect.h" #include <cstdio> #include <unistd.h> #include <cassert> #include <string> #include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define fi first #define se second #define pi pair<int,int> #define mp make_pair typedef long long ll; const int inf=0x3f3f3f3f; const ll linf=1e18; const int N=2500+1; const double eps=1e-5; const int mo=1e9+7; int n,m; ll a[N][N]; struct node { int pos; ll v; }; node b[N]; int c[N],c2[N]; vector<int> e[N][N],e2[N][N]; bool cmp(node x,node y) { if (x.v==y.v) return x.pos<y.pos; return x.v>y.v; } vector<node> bit_q[N][N]; // q的树状数组 int l_max[N][N],u_max[N][N]; struct point { int x,y; }; vector<point> Q[N][N]; int far_up[N][N]; ll res; int lowbit(int x) { return x&-x; } void add(int x,int v,int len) { int t=x; while (x<=len) { c[x]=max(c[x],v); x+=lowbit(x); } x=len-t+1; while (x<=len) { c2[x]=min(c2[x],v); x+=lowbit(x); } } int getmax(int x) { int ans=0; while (x>=1) { ans=max(ans,c[x]); x-=lowbit(x); } return ans; } int getmin(int x,int len) { x=len-x+1; int ans=inf; while (x>=1) { ans=min(ans,c2[x]); x-=lowbit(x); } return ans; } void uniquelize() { int sz; FOR(i,n) FOR(j,m) { vector<int> &v=e[i][j]; sz=v.size(); FOR(k,sz/2) { swap(v[k-1],v[sz-k]); } //sort(v.begin(),v.end()); //v.erase(unique(v.begin(),v.end()),v.end()); } FOR(i,m) FOR(j,n) { vector<int> &v=e2[i][j]; sz=v.size(); FOR(k,sz/2) { swap(v[k-1],v[sz-k]); } //sort(v.begin(),v.end(),greater<int>()); //v.erase(unique(v.begin(),v.end()),v.end()); } } void get_valid_interval() { int p,pos,l,r,old_l,old_r; FOR(i,n) { FOR(j,m) c[j]=0,c2[j]=inf; FOR(j,m) b[j].pos=j,b[j].v=a[i][j]; sort(b+1,b+1+m,cmp); p=1,old_l=old_r=0; FOR(j,m) { if (j==m||b[j].v!=b[j+1].v) { for (int k=p;k<=j;k++) { pos=b[k].pos; if (old_l<=pos&&pos<=old_r) continue; l=getmax(pos); if (l==0) continue; r=getmin(pos,m); if (r==inf) continue; old_l=l,old_r=r; l++;r--; e[i][l].pb(r); } for (int k=p;k<=j;k++) { pos=b[k].pos; add(pos,pos,m); } p=j+1,old_l=old_r=0; } } } FOR(j,m) { FOR(i,n) c[i]=0,c2[i]=inf; FOR(i,n) b[i].pos=i,b[i].v=a[i][j]; sort(b+1,b+1+n,cmp); p=1,old_l=old_r=0; FOR(i,n) { if (i==n||b[i].v!=b[i+1].v) { for (int k=p;k<=i;k++) { pos=b[k].pos; if (old_l<=pos&&pos<=old_r) continue; l=getmax(pos); if (l==0) continue; r=getmin(pos,n); if (r==inf) continue; old_l=l,old_r=r; l++;r--; e2[j][r].pb(l); } for (int k=p;k<=i;k++) { pos=b[k].pos; add(pos,pos,n); } p=i+1,old_l=old_r=0; } } } } void get_Q(){ int x,y,sz; FOR(i,n) { FOR(j,m) { sz=int(e2[j][i].size()); y=j; for (int k=0;k<sz;k++) { x=e2[j][i][k]; l_max[x][y]=l_max[x][y-1]+1; Q[x][y-l_max[x][y]+1].pb(point{i,j}); } } FOR(j,m) { sz=int(e2[j][i].size()); y=j; for (int k=0;k<sz;k++) { x=e2[j][i][k]; l_max[x][y]=0; } } } } void get_bit_q() { int sz; FOR(i,n) FOR(j,m) { sz=int(e2[j][i].size()); for (int k=0;k<sz;k++) { bit_q[i][j].pb(node{e2[j][i][k],0}); } } } void add2(vector<node> &a,int x,int v) { int sz=int(a.size()); while (x<=sz) { a[x-1].v+=v; x+=lowbit(x); } } int getsum(vector<node> &a,int x) { int ans=0; while (x>=1) { ans+=a[x-1].v; x-=lowbit(x); } return ans; } long long count_rectangles(std::vector<std::vector<int> > aa) { int i,j,k,x,y,sz,px,py,l,r,mid,ok_mid; n=aa.size(); m=aa[0].size(); for (i=1;i<=n;i++) { for (j=1;j<=m;j++) { a[i][j]=aa[i-1][j-1]; } } get_valid_interval(); uniquelize(); get_Q(); get_bit_q(); point q; for (j=1;j<=m;j++) { for (i=1;i<=n;i++) { sz=int(e[i][j].size()); for (k=0;k<sz;k++) { y=e[i][j][k]; u_max[i][y]=u_max[i-1][y]+1; far_up[i][y]=x-u_max[i][y]+1; } } for (i=1;i<=n;i++) { sz=int(e[i][j].size()); for (k=0;k<sz;k++) { y=e[i][j][k]; u_max[i][y]=0; } } for (i=1;i<=n;i++) { sz=Q[i][j].size(); for (k=0;k<sz;k++) { q=Q[i][j][k]; x=q.x,y=q.y; px=i,py=q.y; l=1,r=int(e2[y][x].size()); ok_mid=0; // 找最小的>=px的数字 while (l<=r) { mid=(l+r)/2; if (e2[y][x][mid-1]>=px) { l=mid+1; ok_mid=mid; } else r=mid-1; } if (ok_mid) add2(bit_q[x][y],ok_mid,1); } } for (i=1;i<=n;i++) { sz=int(e[i][j].size()); for (k=0;k<sz;k++) { y=e[i][j][k]; l=1,r=int(e2[y][i].size()); ok_mid=0; while (l<=r) { mid=(l+r)/2; if (e2[y][i][mid-1]>=far_up[i][y]) { l=mid+1; ok_mid=mid; } else r=mid-1; } if (ok_mid) { res+=getsum(bit_q[i][y],ok_mid); } } } } return res; } /* class InputReader { private: static const int SIZE = 4096; int inputFileDescriptor; char buf[SIZE]; int curChar; int numChars; public: inline InputReader(int _inputFileDescriptor): inputFileDescriptor(_inputFileDescriptor), curChar(0), numChars(0) { } inline void close() { ::close(inputFileDescriptor); } inline char read() { assert(numChars != -1); if (curChar >= numChars) { curChar = 0; numChars = ::read(inputFileDescriptor, buf, SIZE); if (numChars == -1) return -1; } return buf[curChar++]; } inline int readInt() { int c = eatWhite(); int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int res = 0; do { assert(c >= '0' && c <= '9'); res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } inline string readString() { char c = eatWhite(); string res; do { res += c; c = read(); } while (!isSpaceChar(c)); return res; } inline string readLine() { string res; while (true) { char c = read(); if (c == '\n' || c == '\r' || c == -1) break; res += c; } return res; } inline char eatWhite() { char c = read(); while (isSpaceChar(c)) c = read(); return c; } static inline bool isSpaceChar(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } }; int main() { InputReader inputReader(STDIN_FILENO); int n, m; n = inputReader.readInt(); m = inputReader.readInt(); vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] = inputReader.readInt(); } } inputReader.close(); long long result = count_rectangles(a); printf("%lld\n", result); fclose(stdout); return 0; }*/

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:202:22: warning: variable 'py' set but not used [-Wunused-but-set-variable]
  202 |  int i,j,k,x,y,sz,px,py,l,r,mid,ok_mid;
      |                      ^~
rect.cpp:222:19: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |     far_up[i][y]=x-u_max[i][y]+1;
      |                  ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...