Submission #154394

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
154394	2019-09-21 16:28:17	bruce_test	Rectangles (IOI19_rect)	C++14	100 / 100	4105 ms	807804 KiB

rect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt,tune=native"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
#define f first
#define s second
const int MM = 2505;
int N, M, a[MM][MM], st[MM], top, l[MM], r[MM], u[MM], d[MM], toclear[MM], cnt; ll bit[MM], ans;
vector<pi> h[MM][MM], v[MM][MM];
bool cmp(pi x, pi y){ return x.s < y.s; }
void upd(int x, int val){
    for(int i=x; i<MM; i+=i&-i) bit[i] += val;
}
ll qry(int x){
    ll sum = 0;
    for(int i=x; i; i-=i&-i) sum += bit[i];
    return sum;
}
long long count_rectangles(std::vector<std::vector<int>> x){
    N = x.size(); M = x[0].size();
    for(int i=1; i<=N; i++){
        top = 0;
        for(int j=1; j<=M; j++){
            a[i][j] = x[i-1][j-1];
            while(top > 0 && a[i][st[top]] < a[i][j]) top--;
            l[j] = st[top]; st[++top] = j;
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:55:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int p=0, q=0; p<h[i][j].size(); p++){
                                   ~^~~~~~~~~~~~~~~
rect.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(q < h[i+1][j].size() && h[i+1][j][q].f < h[i][j][p].f) q++;
                           ~~^~~~~~~~~~~~~~~~~~
rect.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(q < h[i+1][j].size() && h[i+1][j][q].f == h[i][j][p].f) h[i][j][p].s = h[i+1][j][q].s+1;
                        ~~^~~~~~~~~~~~~~~~~~
rect.cpp:62:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int p=0, q=0; p<v[i][j].size(); p++){
                                   ~^~~~~~~~~~~~~~~
rect.cpp:63:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(q<v[i][j+1].size() && v[i][j+1][q].f < v[i][j][p].f) q++;
                           ~^~~~~~~~~~~~~~~~~
rect.cpp:64:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(q<v[i][j+1].size() && v[i][j+1][q].f == v[i][j][p].f) v[i][j][p].s = v[i][j+1][q].s+1;
                        ~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28