| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577621 |
2022-06-15T06:38:14 Z |
lollipop |
Poklon (COCI17_poklon) |
C++17 |
|
5000 ms |
20044 KB |
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
#define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
using namespace std ;
const int mod1 = 1000000007 ;
const int mod = 998244353 ;
const int N = 2e5 + 10 ;
map < int , int > ma , ma1 ;
int block = 800 ;
struct stu{
int f ;
int s ;
int indx ;
};
int qu[ 500005 ] ;
bool sortby( stu p , stu p1 ){
if( p.f / block == p1.f / block ) return p.s < p1.s ;
else return ( p.f / block ) < ( p1.f / block ) ;
}
int ans = 0 ;
int a[ 500005 ] ;
void addR( int i ){
if( ma[ a[ i ] ] == 2 ) ans -- ;
if( ma[ a[ i ] ] == 1 ) ans ++ ;
ma[ a[ i ] ] ++ ;
}
void delR( int i ){
if( ma[ a[ i ] ] == 3 ) ans ++ ;
if( ma[ a[ i ] ] == 2 ) ans -- ;
ma[ a[ i ] ] -- ;
}
void addL( int i ){
if( ma[ a[ i ] ] == 2 ) ans -- ;
if( ma[ a[ i ] ] == 1 ) ans ++ ;
ma[ a[ i ] ] ++ ;
}
void delL( int i ){
if( ma[ a[ i ] ] == 3 ) ans ++ ;
if( ma[ a[ i ] ] == 2 ) ans -- ;
ma[ a[ i ] ] -- ;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n , q ;
cin >> n >> q ;
FOR( i , n ) cin >> a[ i + 1 ] ;
vector < stu > v ;
// block = ( n / sqrt( q ) ) ;
FOR( i , q ){
int x , y ; cin >> x >> y ;
v.pb( { x , y , i } ) ;
}
sort( v.begin() , v.end() , sortby ) ;
int l = 1 , r = 0 ;
for( int i = 0 ; i < v.size() ; i ++ ){
int L = v[ i ].f ;
int R = v[ i ].s ;
while( l < L ){
delL( l ) ;
l ++ ;
}
while( l > L ){
l -- ;
addL( l ) ;
}
while( R > r ){
r ++ ;
addR( r ) ;
}
while( R < r ){
delR( r ) ;
r -- ;
}
qu[ v[ i ].indx ] = ans ;
}
FOR( i , q ) cout << qu[ i ] << "\n" ;
}
Compilation message
poklon.cpp:10: warning: "FOR" redefined
10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
|
poklon.cpp:9: note: this is the location of the previous definition
9 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
|
poklon.cpp:11: warning: "FOR" redefined
11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
|
poklon.cpp:10: note: this is the location of the previous definition
10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
|
poklon.cpp: In function 'int main()':
poklon.cpp:63:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<stu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for( int i = 0 ; i < v.size() ; i ++ ){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
5 ms |
372 KB |
Output is correct |
| 3 |
Correct |
17 ms |
400 KB |
Output is correct |
| 4 |
Correct |
92 ms |
660 KB |
Output is correct |
| 5 |
Correct |
2632 ms |
4524 KB |
Output is correct |
| 6 |
Correct |
3616 ms |
4508 KB |
Output is correct |
| 7 |
Execution timed out |
5097 ms |
8172 KB |
Time limit exceeded |
| 8 |
Execution timed out |
5101 ms |
15108 KB |
Time limit exceeded |
| 9 |
Execution timed out |
5072 ms |
16048 KB |
Time limit exceeded |
| 10 |
Execution timed out |
5081 ms |
20044 KB |
Time limit exceeded |
