제출 #443413

#제출 시각아이디문제언어결과실행 시간메모리
443413vanicRectangles (IOI19_rect)C++14
컴파일 에러
0 ms0 KiB
#include "rect.h" #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <map> using namespace std; typedef long long ll; const int maxn=2503, Log=12, pot=(1<<Log); const int inf=1e9; int R1[maxn][maxn][Log], C1[maxn][maxn][Log], R2[maxn][maxn][Log], C2[maxn][maxn][Log], R3[maxn][maxn][Log], C3[maxn][maxn][Log], R4[maxn][maxn][Log], C4[maxn][maxn][Log]; int gore[maxn][Log], dolje[maxn][Log]; ll sol; int svi[maxn][maxn][4]; int n, m; map < ll, bool > bio; int svi1[maxn][maxn][4]; int query1(int y, int l, int d){ int raz=d-l+1; int x=log2(raz); return min(R1[y][l][x], R2[y][d][x]); } int query2(int y, int l, int d){ int raz=d-l+1; int x=log2(raz); return max(R3[y][l][x], R4[y][d][x]); } int query3(int y, int l, int d){ int raz=d-l+1; int x=log2(raz); return min(C1[l][y][x], C2[d][y][x]); } int query4(int y, int l, int d){ int raz=d-l+1; int x=log2(raz); return max(C3[l][y][x], C4[d][y][x]); } ll count_rectangles(vector < vector < int > > a){ n=a.size(); m=a[0].size(); vector < pair <int, int > > v; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][2]=0; } else{ svi1[i][j][2]=v.back().second+1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][2]=0; } else{ svi[i][j][2]=v.back().second+1; } v.push_back({a[i][j], j}); } v.clear(); for(int j=m-1; j>-1; j--){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][3]=m-1; } else{ svi1[i][j][3]=v.back().second-1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][3]=m-1; } else{ svi[i][j][3]=v.back().second-1; } v.push_back({a[i][j], j}); } v.clear(); } for(int j=0; j<m; j++){ for(int i=0; i<n; i++){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][0]=0; } else{ svi1[i][j][0]=v.back().second+1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][0]=0; } else{ svi[i][j][0]=v.back().second+1; } v.push_back({a[i][j], i}); } v.clear(); for(int i=n-1; i>-1; i--){ while(!v.empty() && v.back().first<a[i][j]){ v.pop_back(); } if(v.empty()){ svi1[i][j][1]=n-1; } else{ svi1[i][j][1]=v.back().second-1; } while(!v.empty() && v.back().first<=a[i][j]){ v.pop_back(); } if(v.empty()){ svi[i][j][1]=n-1; } else{ svi[i][j][1]=v.back().second-1; } v.push_back({a[i][j], i}); } v.clear(); } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ R1[i][j][0]=svi1[i][j][1]; R2[i][j][0]=svi1[i][j][1]; R3[i][j][0]=svi1[i][j][0]; R4[i][j][0]=svi1[i][j][0]; C1[i][j][0]=svi1[i][j][3]; C2[i][j][0]=svi1[i][j][3]; C3[i][j][0]=svi1[i][j][2]; C4[i][j][0]=svi1[i][j][2]; } } for(int i=0; i<m; i++){ gore[i][0]=min(i+1, m-1); dolje[i][0]=max(i-1, 0); } for(int i=1; i<Log; i++){ for(int j=0; j<m; j++){ gore[j][i]=gore[gore[j][i-1]][i-1]; dolje[j][i]=dolje[dolje[j][i-1]][i-1]; for(int k=0; k<n; k++){ R1[k][j][i]=min(R1[k][j][i-1], R1[k][gore[j][i-1]][i-1]); R2[k][j][i]=min(R2[k][j][i-1], R2[k][dolje[j][i-1]][i-1]); R3[k][j][i]=max(R3[k][j][i-1], R3[k][gore[j][i-1]][i-1]); R4[k][j][i]=max(R4[k][j][i-1], R4[k][dolje[j][i-1]][i-1]); } } } for(int i=0; i<n; i++){ gore[i][0]=min(i+1, n-1); dolje[i][0]=max(i-1, 0); } for(int i=1; i<Log; i++){ for(int j=0; j<n; j++){ gore[j][i]=gore[gore[j][i-1]][i-1]; dolje[j][i]=dolje[dolje[j][i-1]][i-1]; for(int k=0; k<m; k++){ C1[j][k][i]=min(C1[j][k][i-1], C1[gore[j][i-1]][k][i-1]); C2[j][k][i]=min(C2[j][k][i-1], C2[dolje[j][i-1]][k][i-1]); C3[j][k][i]=max(C3[j][k][i-1], C3[gore[j][i-1]][k][i-1]); C4[j][k][i]=max(C4[j][k][i-1], C4[dolje[j][i-1]][k][i-1]); } } } int c[4]; ll br; for(int i=1; i<n-1; i++){ for(int j=1; j<m-1; j++){ br=0; for(int k=0; k<4; k++){ c[k]=svi[i][j][k]; br*=maxn; br+=c[k]; } if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1 || bio.find(br)!=bio.end()){ continue; } /* if(i==3 && j==3){ cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << c[3] << endl; // cout << query2(c[2], c[3]) << endl; }*/ if(c[0]<query2(c[1]+1, c[2], c[3])){ continue; } if(c[1]>query1(c[0]-1, c[2], c[3])){ continue; } if(c[2]<query4(c[3]+1, c[0], c[1])){ continue; } if(c[3]>query3(c[2]-1, c[0], c[1])){ continue; } bio[br]=1; // cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl; sol++; } } return sol; }

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

/tmp/cclHMf2t.o: in function `query1(int, int, int)':
rect.cpp:(.text+0x5a): relocation truncated to fit: R_X86_64_PC32 against symbol `R1' defined in .bss section in /tmp/cclHMf2t.o
/tmp/cclHMf2t.o: in function `count_rectangles(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
rect.cpp:(.text+0x888): relocation truncated to fit: R_X86_64_PC32 against symbol `R1' defined in .bss section in /tmp/cclHMf2t.o
rect.cpp:(.text+0x9a0): relocation truncated to fit: R_X86_64_PC32 against symbol `R1' defined in .bss section in /tmp/cclHMf2t.o
rect.cpp:(.text+0x1022): relocation truncated to fit: R_X86_64_PC32 against symbol `R1' defined in .bss section in /tmp/cclHMf2t.o
/tmp/cclHMf2t.o: in function `_GLOBAL__sub_I_R1':
rect.cpp:(.text.startup+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
rect.cpp:(.text.startup+0x25): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status